模拟
栈的特点是「先进后出」,队列的特点是「先进先出」。
设定两个栈 stackA
、stackB
,这里为了逻辑清晰,规定入队操作都在 stackA
进行,出队操作都在 stackB
进行。
初始队列为空,执行入队操作,则队首元素会被压入 stackA
栈底,后续入队元素依次压入 stackA
中。
执行出队操作时,由于队首元素压在 stackA
栈底,怎么保证队列「先进先出」的性质呢?我们先把 stackA
中的元素依次出栈并在 stackB
入栈,这样队首元素就会在 stackB
的栈顶,此时再执行出队操作即可。
上述操作总结起来就是:
push
:直接在stackA
中压入元素。pop
:直接从stackB
中弹出元素;如果stackB
为空,则先把stackA
中的元素倒入stackB
中,再从stackB
中弹出元素。peek
:直接查看stackB
的栈顶元素;如果stackB
为空,则先把stackA
中的元素倒入stackB
中,再查看stackB
的栈顶元素。isEmpty
:stackA
和stackB
同时为空则队列为空,否则队列不为空。
时空复杂度
- 时间复杂度:
- 空间复杂度:
Java 代码
class MyQueue {
// 入队操作都在 stackA 进行,出队操作都在 stackB 进行
Deque<Integer> stackA, stackB;
/** Initialize your data structure here. */
public MyQueue() {
stackA = new LinkedList<Integer>();
stackB = new LinkedList<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stackA.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
// 如果 stackB 为空,则先把 stackA 中的元素倒入 stackB 中
if (stackB.isEmpty()) {
while (!stackA.isEmpty()) {
stackB.push(stackA.pop());
}
}
return stackB.pop();
}
/** Get the front element. */
public int peek() {
// 如果 stackB 为空,则先把 stackA 中的元素倒入 stackB 中
if (stackB.isEmpty()) {
while (!stackA.isEmpty()) {
stackB.push(stackA.pop());
}
}
return stackB.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackA.isEmpty() && stackB.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/