【算法系列-栈与队列】栈与队列的双向模拟

欢迎来到【算法系列】第五弹 🏆 栈与队列，接下来我们将围绕栈与队列这类型的算法题进行解析与练习！一起加油吧！！( •̀ ω •́ )✧✨

文章目录

【算法系列-栈与队列】栈与队列的双向模拟
- 1. 用栈实现队列(LeetCode 232)
- - 1.1 思路分析🎯
  - 1.2 解题过程🌰
  - 1.3 代码示例✨
- 2.用队列实现栈(LeetCode 225)
- - 2.1 思路分析🎯
  - 2.2 代码示例🌰

1. 用栈实现队列(LeetCode 232)

【题目链接】232. 用栈实现队列 - 力扣（LeetCode）

1.1 思路分析🎯

这里使用两个栈来实现队列：一个栈stackIn用来添加元素，另一个栈stackOut用来弹出元素

1.2 解题过程🌰

队列添加元素：将元素添加到stackIn即可； 队列弹出元素：

若stackOut不为空，此时的stackOut栈顶元素即为队首元素，弹出即可；
若stackOut为空，先将stackIn中的所有元素都弹出并添加到stackOut中，遍历完后stackOut的栈顶元素即为需要弹出的队首元素，符合队列的先进先出，弹出即可；5

队列返回队首元素：

若stackOut不为空，此时的stackOut栈顶元素即为队首元素，返回即可；
若stackOut为空，重复上述过程将stackIn中的所有元素都弹出并添加到stackOut中，并返回stackOut栈顶元素即可

队列判断是否为空队列：若两个栈都为空则队列为空，否则队列不为空

1.3 代码示例✨

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        initQueue();
        return stackOut.pop();
    }
    
    public int peek() {
        initQueue();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    public void initQueue() {
        if (!stackOut.isEmpty()) {
            return;
        }
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

2.用队列实现栈(LeetCode 225)

【题目链接】225. 用队列实现栈 - 力扣（LeetCode）

2.1 思路分析🎯

这道题可以有两种方式进行模拟，一种使用单队列，一种使用双队列，这里针对使用单队列的方式进行模拟实现栈：

这里使用了一个队列来实现栈，比较方便快捷，单队列实现栈的操作方式需要注意的就是如何找到栈顶元素，思路就是将队列前 size - 1 个元素移除后重新加入队列，这样等到最后遍历完此时的队首元素就是栈顶元素了

2.2 代码示例🌰

单队列实现栈的代码如下：

class MyStack {
    
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
    }
    
    public int pop() {
        initQueue();
        return queue.poll();
    }
    
    public int top() {
        initQueue();
        // 队列的入口处的第一个元素即栈顶元素，通过将队列元素重新插入队列来将这个栈顶元素拍到出口处，
        // 记录下结果后仍需要将这个元素重新插入队尾
        int ret = queue.poll();
        queue.offer(ret);
        return ret;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    // 将队列元素重新插入队列，最后的队首元素即为栈顶元素
    public void initQueue() {
        int size = queue.size();
        size--;
        while (size > 0) {
            queue.offer(queue.poll());
            size--;
        }
    }
}

双队列实现栈的代码如下：

class MyStack {

    Queue<Integer> q1;
    Queue<Integer> q2;


    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    /*入栈*/
    public void push(int x) {
        if(!q1.isEmpty()) {
            q1.offer(x);
        }
        else if(!q2.isEmpty()) {
            q2.offer(x);
        }
        else {
            q1.offer(x);
        }
    }

    /*出栈*/
    public int pop() {

        if (empty()) {
            return -1;
        }

        if (!q1.isEmpty()) {
            int size = q1.size();
            for (int i = 0;i < size - 1;i++) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
        else {
            int size = q2.size();
            for (int i = 0;i < size -1;i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }
    }

    /*获取栈顶元素*/
    public int top() {
        if (empty()) {
            return -1;
        }

        if (!q1.isEmpty()) {
            int size = q1.size();
            int x = -1;
            for (int i = 0;i < size;i++) {
                x = q1.poll();
                q2.offer(x);
            }
            return x;
        }
        else {
            int size = q2.size();
            int  x = -1;
            for (int i = 0;i < size;i++) {
                x = q2.poll();
                q1.offer(x);
            }
            return x;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}