【栈和队列专题】—— 双队列模拟栈

LeetCode 225 : 用队列实现栈

队列

1.一些关于队列的基本操作

• 向队列中添加元素[3种方法]

queue.add(value)
queue.offer(value)
queue.put(value)

• 删除队首元素

queue.remove()
queue.poll()
queue.take()

• 查看队首元素

queue.element()
queue.peek()

• 判断队列是否为空

queue.isEmpty()

2.队列的实现
（1）可以通过链表来实现队列
（2）可以通过Java中的LinkedList来实现队列
（3）也可以通过栈来模拟队列

队列实现栈

️ 解题思路：
（1）用队列模拟栈最重要的就是来完成元素顺序的控制，队列中怎样的元素存储顺序才能和栈相同呢？

（2）栈的主要特点就是后入先出，队列只能通过让实际后入的元素先存储到队列中，这样就满足了后入先出的性质，那么如何才能让后入的元素来先保存到队列中呢？

（3）设置两个队列，一个主队列、一个辅助队列。将新添加的元素保存到辅助队列之中，然后让主队列中的元素全部取出保存到辅助队列中，最后再交换两个队列。这样就保证了实际后入的元素先存储到了队列中。

️ 代码部分:

class MyStack {
    

    /* 通过两个队列来模拟栈的操作，重点元素如何保证在队列中存储元素的顺序 与和栈中存储元素的顺序构成逆序关系 */

    //定义两个队列
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
    
        /*因为通过队列来模拟栈，所以构造方法中主要是完成两个队列的创建 */
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
    
        queue2.add(x);
         //将主队列中的元素取出放到辅助队列中
        while(!queue1.isEmpty()){
    
            queue2.add(queue1.remove());
        }

        //交换两个队列
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;

    }
    
    public int pop() {
    
        /*对于队列中元素的保存顺序和栈是相同的，所以移除栈顶元素就是 删除队首元素 */
        return queue1.remove();
    }
    
    public int top() {
    
        /*与取出队首元素相同 */
        return queue1.element();
    }
    
    public boolean empty() {
    
        /*判断栈是否为空也是判断队列是否为空 */
        return queue1.isEmpty();
    }
}

/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */