括号匹配，栈实现队列，队列实现栈以及循环队列

思路

1. 利用栈的先进后出特性
2. 左括号入栈
3. 遇到右括号，这是就应该开始一一对比
4. 不相等的情况无非是括号不匹配, 左括号多,右括号多
5. 三种情况全部排查完毕之后则说明括号完全匹配

private static boolean isValid(String str) {
        if (str.length() == 0 || str.length() % 2 != 0) {
            return false;
        } else if (str == null) {
            return false;
        } else {
            Stack stack = new Stack<>();
            
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch == '{' || ch == '[' || ch == '(') {
                    stack.push(ch);
                } else{// 遇到右括号
                    // 栈为空
                    if (stack.empty()) {// 【右括号多】
                        return false;
                    } else {
                        // 栈不为空
                        char tmp = stack.peek();
                        if (tmp == '{' && ch == '}' || tmp == '[' && ch == ']' || tmp == '(' && ch == ')'){
                            stack.pop();// 相等就弹出
                        }else{
                            return false;// 左右括号不匹配
                        }
                    }
                }
            }
            if (!stack.empty()){
                return false;// 左括号多
            }
            return true;
        }
    }

思路

1. 利用两个队列，只需要让不为空的进出队列即可
2. 如果两个队列都不为空，则让其中某一个队列存储元素
3. peek 和 pop 操作记得控制好 空 这一边界条件

public class MyStack {
    public Queue qu1 = new linkedList<>();
    public Queue qu2 = new linkedList<>();

    
    public void push(int x) {
        if (!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        } else {
            qu1.offer(x);
        }
    }

    
    public int pop() {
        if (empty()) {
            return -1;
        }
        int e = -1;
        if (!qu1.isEmpty()) {
            int sz = qu1.size() - 1;
            while (sz-- != 0) {
                e = qu1.poll();
                qu2.offer(e);
            }
            e = qu1.poll();
        } else {
            int sz = qu2.size() - 1;
            while (sz-- != 0) {
                e = qu2.poll();
                qu1.offer(e);
            }
            e = qu2.poll();
        }
        return e;
    }

    
    public int top() {
        if (empty()){
            return -1;
        }else{
            int e = -1;
            if (!qu1.isEmpty()){
                int sz = qu1.size();
                while(sz--!=0){
                    e = qu1.poll();
                    qu2.offer(e);
                }
            }else{
                int sz = qu1.size();
                while(sz--!=0){
                    e = qu1.poll();
                    qu2.offer(e);
                }
            }
            return e;
        }
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

在这里插入图片描述

如图所示就是一次“出栈pop”操作

1. ABCDEF 先入队列
2. 把一个不为空的队列queue1元素 ABCDE 搬入到另一个队列queue2中
3. queue1 再出队列，这样就实现了“先进后出【后进先出】”的功能

两个指定的栈实现队列

只需要制定一个栈入一个栈出即可达到队列的先进先出效果

public class MyyQueue {
    Stack stack1 = new Stack<>();
    Stack stack2 = new Stack<>();
    public void push(int x){
        stack1.push(x);
    }
    public int pop(){
        if (empty()){
            return -1;
        }else {
            if (stack2.empty()){
                while (!stack1.empty()){// 把栈1出完全部存入栈2
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();//弹出栈2栈顶元素
        }
    }
    public int peek(){
        if (empty()){
            return -1;
        }else {
            if (stack2.empty()){
                while (!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }
    }
    public boolean empty(){
        return stack1.empty() && stack2.empty();
    }
}

设计两个栈

1. 一个栈 stack存储所有元素, minStack只存储stack当前中小的元素，按次序存储

public class MinStack {
    Stack stack = new Stack<>();
    Stack minStack = new Stack<>();
    public void push(int val){
        stack.push(val);
        if (minStack.empty()){
            minStack.push(val);
        }else{
            if (minStack.peek() <= val){// 如果存储了两个比 minStack 栈顶还小的元素，当 stack 弹出栈中的元素刚好和 minStack 栈顶一样的时候两个都需要弹出，因此需要包含相同的最小值存入 minStack 中
                minStack.push(val);
            }
        }
    }

    public void pop(){
        if (stack.pop() == minStack.peek()){
            minStack.pop();// 不可以把 minStack 的元素忽略掉
        }
    }
    public int top(){
        return stack.peek();
    }

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

循环队列的详细剖析请查看我之前博客内容

class MyCircularQueue {
    private int[] elem;
    private int front, rear;

    public MyCircularQueue(int k) {
        this.elem = new int[k+1];
    }


    
    public boolean enQueue(int value) {
        if ((this.rear + 1) % this.elem.length == this.front) {
            return false;//满了
        } else {
            this.elem[this.rear] = value;
            this.rear = (this.rear + 1) % this.elem.length;
            return true;
        }
    }

    
    public boolean deQueue() {
        if (this.front == this.rear) {
            return false;
        } else {
            int val = this.elem[this.front];
//            this.front = (this.front + 1) % this.elem.length;// 因为是循环，所以不能直接 front+1
            return true;
        }
    }

    
    public int Front() {
        if (this.front == this.rear) {
            return -1;// leetcode 抛异常会认为是你的代码错误，所以不能抛异常
        } else {
            int val = this.elem[this.front];
            return val;
        }
    }

    
    public int Rear() {
        if (this.rear == this.front) {
            return -1;
        } else {
            if (this.rear == 0) {
                return this.elem[this.elem.length - 1];
            } else {
                return this.elem[this.rear - 1];
            }
        }
    }

    public boolean isEmpty() {
        return this.front == this.rear;
    }

    public boolean isFull() {
        return this.rear + 1 == this.front;
    }
}