怎么用Java栈实现队列

147次阅读

共计 1277 个字符，预计需要花费 4 分钟才能阅读完成。

使用 Java 的栈来实现队列可以通过两个栈来实现。一个栈用来存储队列的元素，另一个栈用来辅助操作。

具体实现步骤如下：

创建两个栈，一个用于存储队列的元素，命名为stack1，另一个用于辅助操作，命名为stack2。
实现队列的入队操作 enqueue，即将元素添加到stack1 中。
实现队列的出队操作 dequeue，首先判断stack2 是否为空，若为空，则将 stack1 中的元素依次弹出并压入 stack2 中，然后从 stack2 中弹出栈顶元素作为出队元素；若 stack2 不为空，则直接从 stack2 中弹出栈顶元素作为出队元素。
实现队列的获取队首元素操作 peek，同样需要先判断stack2 是否为空，若为空，则将 stack1 中的元素依次弹出并压入 stack2 中，然后获取 stack2 的栈顶元素作为队首元素；若 stack2 不为空，则直接获取 stack2 的栈顶元素作为队首元素。
实现队列的判空操作 isEmpty，判断stack1 和stack2是否都为空，若是，则队列为空；否则，队列不为空。

下面是 Java 代码的实现：

import java.util.Stack;

public class QueueWithStacks {private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public QueueWithStacks() {stack1 = new Stack<>();
        stack2 = new Stack<>();}

    public void enqueue(int element) {stack1.push(element);
    }

    public int dequeue() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());
            }
        }
        return stack2.pop();}

    public int peek() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());
            }
        }
        return stack2.peek();}

    public boolean isEmpty() {return stack1.isEmpty() && stack2.isEmpty();
    }
}

使用示例：

public class Main {public static void main(String[] args) {QueueWithStacks queue = new QueueWithStacks();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.dequeue());  // 输出: 1
        System.out.println(queue.peek());  // 输出: 2
        System.out.println(queue.isEmpty());  // 输出: false
    }
}