【数据结构】队列和栈相互实现

1.用队列实现栈

这个类使用两个队列来模拟栈的行为，其中一个队列用于主要操作（queue1），另一个队列作为辅助（queue2）。通过这种方式，我们可以确保栈的后进先出（LIFO）特性。

class MyStack {

    // 用于存储元素的主要队列
    private Queue<Integer> queue1;
    
    // 用于辅助操作的队列
    private Queue<Integer> queue2;

    // 构造函数，初始化两个队列
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    // 将元素压入栈顶
    public void push(int x) {
        // 将新元素添加到辅助队列 queue2 中
        queue2.offer(x);
        
        // 将 queue1 中的所有元素转移到 queue2 中
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        
        // 交换 queue1 和 queue2 的引用，使得 queue1 总是包含所有元素
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    // 移除并返回栈顶元素
    public int pop() {
        // 从 queue1 中移除并返回顶部元素
        return queue1.poll();
    }
    
    // 返回栈顶元素但不移除
    public int top() {
        // 返回 queue1 的第一个元素，即栈顶元素
        return queue1.peek();
    }
    
    // 检查栈是否为空
    public boolean empty() {
        // 栈为空当且仅当 queue1 为空
        return queue1.isEmpty();
    }
}

代码解释

• 构造函数 (MyStack): 初始化两个队列 queue1 和 queue2。这两个队列将被用来模拟栈的行为。
• push 方法:
  新元素首先被添加到 queue2 中。
  然后，queue1 中的所有元素被逐个移动到 queue2 中。
  最后，交换 queue1 和 queue2 的引用。这样做的目的是确保 queue1 总是包含所有的元素，并且新加入的元素总是在 queue1 的前端，从而模拟了栈的 LIFO 行为。
• pop 方法:
  直接从 queue1 中移除并返回队头元素。由于 queue1 中的元素顺序已经被调整，队头元素就是栈顶元素。
• top 方法:
  返回 queue1 的第一个元素，但不移除它。这是当前栈顶的元素。
• empty 方法:
  判断栈是否为空，只需要检查 queue1 是否为空即可，因为 queue1 始终保存着所有元素。

这种设计利用了队列的先进先出（FIFO）特性来模拟栈的后进先出（LIFO）行为。通过在每次插入时将所有元素转移到另一个队列中，可以保证新插入的元素始终位于队列的前端，从而实现了栈的功能。

2.用栈实现队列

这个类使用两个栈来模拟队列的行为，其中一个栈用于入队操作（inStack），另一个栈用于出队操作（outStack）。通过这种方式，我们可以确保队列的先进先出（FIFO）特性。

class MyQueue {
    
    // 用于处理入队操作的栈
    private Stack<Integer> inStack;
    
    // 用于处理出队操作的栈
    private Stack<Integer> outStack;

    // 构造函数，初始化两个栈
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    // 将元素添加到队尾
    public void push(int x) {
        // 元素直接加入到 inStack 中
        inStack.push(x);
    }
    
    // 移除并返回队头元素
    public int pop() {
        // 如果 outStack 为空，则将 inStack 的所有元素转移到 outStack 中
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        // 从 outStack 弹出并返回顶部元素
        return outStack.pop();
    }
    
    // 返回队头元素但不移除
    public int peek() {
        // 如果 outStack 为空，则将 inStack 的所有元素转移到 outStack 中
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        // 返回 outStack 的顶部元素，但不移除
        return outStack.peek();
    }
    
    // 检查队列是否为空
    public boolean empty() {
        // 队列为空当且仅当 inStack 和 outStack 都为空
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

代码解释

• 构造函数 (MyQueue): 初始化两个栈，一个用于入队操作，另一个用于出队操作。
• push 方法: 直接将新元素压入 inStack 中。这是因为在入队时，我们不需要关心队列的顺序，只需简单地把元素放入栈中即可。
• pop 方法: 当需要出队时，如果 outStack 为空，则将 inStack 中的所有元素转移到 outStack 中。这样做的目的是反转这些元素的顺序，以满足队列的FIFO特性。然后，从 outStack 中弹出顶部元素作为结果。
• peek 方法: 与 pop 方法类似，但如果 outStack 为空，则同样会进行元素转移。不过，peek 只是查看而不移除 outStack 的顶部元素。
• empty 方法: 判断队列是否为空，即两个栈都必须为空时才认为队列为空。

这种设计利用了栈的后进先出（LIFO）特性来实现队列的FIFO行为。通过在需要时将 inStack 中的元素移动到 outStack 中，可以有效地维持正确的出队顺序。