LeetCode-栈和队列专题

1.用栈实现队列

232. Implement Queue using Stacks
     Leetcode

用栈实现队列，因为栈是先进后出的一种数据结构，需要两个栈互相辅助才可以实现队列
in队列负责将元素压到栈中
out队列负责将元素颠倒过来压到栈中
这样就可以用栈实现一个队列了

//2020年10月12日
class MyQueue {

    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        inToOut();
        return out.pop();
    }

    /** Get the front element. */
    public int peek() {
        inToOut();
        return out.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty()&&out.isEmpty();
    }

    public void inToOut(){
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
    }
}

2.用队列实现栈

225. Implement Stack using Queues
     Leetcode

用队列实现栈，因为队列是先进先出的一种数据结构
压栈时需要先将当前元素插入，再将之前插入的元素依次出队入队
这样就可以用队列实现一个栈了

//2020年10月12日
class MyStack {

    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        int count = queue.size();
        while(count-- > 1){
            queue.offer(queue.poll());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }

    /** Get the top element. */
    public int top() {
        return queue.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

3.最小值栈

155. min-stack
     Leetcode

主要思路就是创建一个栈的同时再创建一个记录当前栈最小值的栈

//2020年10月13日
class MinStack {

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

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        s.push(x);
        if(min.isEmpty()){
            min.push(x);
        }else{
            if(min.peek() < x){
                min.push(min.peek());
            }else{
                min.push(x);
            }
        }
    }

    public void pop() {
        s.pop();
        min.pop();
    }

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

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

4.用栈实现括号匹配

20. Valid Parentheses(easy)
    Leetcode

这题我一开始还没想明白，看了一眼解析后明白了
要想实现匹配，左括号和右括号的数量是相等的
而且字符串的一开始不能是右括号

//2020年10月13日
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c == '(' || c == '{' || c == '['){
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char popChar = stack.pop();
                boolean b1 = c == ')' && popChar != '(';
                boolean b2 = c == ']' && popChar != '[';
                boolean b3 = c == '}' && popChar != '{';
                if(b1 || b2 || b3){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

5.每日温度

739. Daily Temperatures (Medium)
     Leetcode

解法1，双重循环

//2020年10月19日
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int a[] = new int[T.length];
        for(int i=0;i<T.length;i++){
            int count = 0;
            for(int j=i+1;j<T.length;j++){
                if(T[j] > T[i]){
                    a[i] = count + 1;
                    break;
                }else if (T[j] <= T[i]){
                    count++;
                }
            }
        }
        return a;
    }
}

解法2，利用栈

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int a[] = new int[T.length];
        Stack<Integer> s = new Stack<>();
        for(int i=0;i<T.length;i++){
            while(!s.isEmpty()&&T[i] > T[s.peek()]){
                int temp = s.pop();
                a[temp] = i - temp;
            }
            s.add(i);
        }
        return a;
    }
}