栈与队列

队列实现栈：https://leetcode-cn.com/problems/implement-stack-using-queues/

class MyStack {

 Queue<Integer> queue = new LinkedList<>();

 public MyStack() {
 }

 public void push(int x) {
     queue.add(x);
 }

 public int pop() {
     //头尾倒置
     for(int i=0;i<queue.size()-1;i++){
         queue.add(queue.poll());
     }
     return queue.poll();
 }

 public int top() {
     //头尾倒置
     for(int i=0;i<queue.size()-1;i++){
         queue.add(queue.poll());
     }
     int result = queue.poll();
     queue.add(result);
     return result;
 }

 public boolean empty() {
     return queue.isEmpty();
 }
}

栈实现队列：https://leetcode-cn.com/problems/implement-queue-using-stacks/

class MyQueue {

 Stack<Integer> stack1 = new Stack<>();
 Stack<Integer> stack2 = new Stack<>();
 public MyQueue() {
 }

 public void push(int x) {
     stack1.push(x);
 }

 public int pop() {
     if(stack2.isEmpty()){
         while(!stack1.isEmpty()){
             stack2.push(stack1.pop());
         }
     }
     if(stack2.isEmpty()){
         return -1;
     }else{
         return stack2.pop();
     }
 }

 public int peek() {
     if(stack2.isEmpty()){
         while(!stack1.isEmpty()){
             stack2.push(stack1.pop());
         }
     }
     if(stack2.isEmpty()){
         return -1;
     }else{
         return stack2.peek();
     }
 }

 public boolean empty() {
     return stack1.isEmpty() && stack2.isEmpty();
 }
}

最小栈：https://leetcode-cn.com/problems/min-stack/

class MinStack {

 Stack<Integer> stack = new Stack<>();
 Stack<Integer> min = new Stack<>();

 public MinStack() {
 }

 public void push(int x) {
     stack.push(x);
     //min栈顶维护最小值
     if(min.isEmpty() || min.peek() >= x){
         min.push(x);
     }
 }

 public void pop() {
     if(stack.pop().equals(min.peek())){
         min.pop();
     }
 }

 public int top() {
     return stack.peek();
 }

 public int getMin() {
     return min.peek();
 }
}

队列的最大值：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

class MaxQueue {

 LinkedList<Integer> queue = new LinkedList<>();
 LinkedList<Integer> max = new LinkedList<>();
 public MaxQueue() {
 }

 public int max_value() {
     if(queue.isEmpty()){
         return -1;
     }else{
         return max.peekFirst();
     }
 }

 public void push_back(int value) {
     queue.addLast(value);
     //max队列的队尾维护最大值，先弹出再存入
     while(!max.isEmpty() && max.peekLast() <= value){
         max.pollLast();
     }
     max.addLast(value);
 }

 public int pop_front() {
     if(queue.isEmpty()){
         return -1;
     }
     int result = queue.pollFirst();
     if(max.peekFirst().equals(result)){
         max.pollFirst();
     }
     return result;
 }
}

有效括号：https://leetcode-cn.com/problems/valid-parentheses/

class Solution {
 public boolean isValid(String s) {
     //单调栈，栈存入右半，如果栈为空或者栈顶不等于下一个字符，则无法闭合，返回false
     Stack<Character> stack = new Stack<>();
     char[] str = s.toCharArray();
     for(char c : str){
         if(c == '('){
             stack.push(')');
         }else if(c == '['){
             stack.push(']');
         }else if(c == '{'){
             stack.push('}');
         }else if(stack.isEmpty() || stack.pop() != c){
             return false;
         }
     }
     //返回栈是否为空
     return stack.isEmpty();
 }
}

最长有效括号：https://leetcode-cn.com/problems/longest-valid-parentheses/

class Solution {
 public int longestValidParentheses(String s) {
     Stack<Integer> stack = new Stack<>();
     //预存-1，用于匹配第一个字符为右半括号的情况
     stack.push(-1);
     char[] str = s.toCharArray();

     int result = 0;
     for(int i=0;i<str.length;i++){
         if(str[i] == '('){
             stack.push(i);
         }else{
             //匹配，弹出栈顶
             stack.pop();
             //如果栈顶弹出后栈为空，从当前位置重新统计，否则计算长度
             if(stack.isEmpty()){
                 stack.push(i);
             }else{
                 result = Math.max(result,i-stack.peek());
             }
         }
     }
     return result;
 }
}

柱状图中最大矩形：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

class Solution {
 public int largestRectangleArea(int[] heights) {

     //复制一个数组，在头尾插入高度为0的柱体
     int[] temp = new int[heights.length+2];
     System.arraycopy(heights,0,temp,1,heights.length);

     Stack<Integer> stack = new Stack<>();
     int result = 0;
     for(int i=0;i<temp.length;i++){
         //找到第一个比栈顶小的元素
         while(!stack.isEmpty() && temp[stack.peek()] > temp[i]){
             //提取栈顶为高
             int high = temp[stack.pop()];
             int width = i - stack.peek()-1;
             result = Math.max(result,high*width);
         }
         stack.push(i);
     }
     return result;
 }
}

每日温度：https://leetcode-cn.com/problems/daily-temperatures/

class Solution {
 public int[] dailyTemperatures(int[] T) {
     Stack<Integer> stack = new Stack<>();
     int[] result = new int[T.length];

     for(int i=0;i<T.length;i++){
         //当前元素比栈顶大时，提取栈顶作为索引，计算天数差值
         while(!stack.isEmpty() && T[stack.peek()] < T[i]){
             int index = stack.pop();
             result[index] = i - index;
         }
         stack.push(i);
     }
     return result;
 }
}

滑动窗口最大值：https://leetcode-cn.com/problems/sliding-window-maximum/

class Solution {
 public int[] maxSlidingWindow(int[] nums, int k) {
     LinkedList<Integer> queue = new LinkedList<>();
     //窗口数组
     int[] result = new int[nums.length - k + 1];
     int index = 0;

     for(int i=0;i<nums.length;i++){
         while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
             queue.pollLast();
         }
         queue.addLast(i);

         //如果左边界i-k == queue.peekFirst()，说明要右移，弹出队首
         if(i-k == queue.peekFirst()){
             queue.pollFirst();
         }
         //如果右边界i >= k-1，要存入
         if(i >= k-1){
             result[index++] = nums[queue.peekFirst()];
         }
     }
     return result;
 }
}