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

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 queue1;
    Queue 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();
    }
}

 解题思路：

（1）设计两个栈，此处定义为A栈与B栈，通过A栈来完成数据的存储，B栈来完成取出/删除队首元素，利用两个栈共同来判断队列是否为空

（2）对于新入队的元素直接添加到A栈中即可

向栈中添加元素有两种方法
stack.add(value)
stack.push(value)

（3）取出队首元素或删除队首元素

• 提取出将元素从A栈转移到B栈中的语句封装为一个方法
• 保证在B栈中，从栈顶到栈底的元素满足元素入队的顺序
• 对于B栈不为空时，是不能将A栈中的元素转移到B栈的，因为这样会破坏元素的顺序

（4）队列判空

• 如果A栈与B栈都为空的情况下，那么返回队列为空
• 元素都转移到了B栈，那么为什么不直接用B栈是否为空来决定队列是否为空呢?

因为此时可能A栈中有一部分元素没有转移到B栈中[对于B栈不为空时，不能转移元素]

 代码部分：

class MyQueue {

    Stack stack1;
    Stack stack2;

    public void stackRemove(){
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
            }
        }
    }
    
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        stackRemove();        
        return stack2.pop();
    }
    
    public int peek() {
        stackRemove();
        return stack2.peek();
    }
    
    public boolean empty() {
        
        return stack2.isEmpty() && stack1.isEmpty();
    }
}