作者 | 程序员小吴
来源 | 五分钟学算法
使用栈实现队列的下列操作:
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
push to top
, peek/pop from top
,size
和 is empty
操作是合法的。这是一道很典型的为初级算法爱好者准备的算法题,首先简单介绍一下 队列 和 栈 这两种数据结构。
队列
队列是一种 先进先出(first in - first out, FIFO)的数据结构,队列中的元素都从后端(rear)入队(push),从前端(front)出队(pop)。
栈
栈是一种 后进先出(last in - first out, LIFO)的数据结构,栈中元素从栈顶(top)压入(push),也从栈顶弹出(pop)。
为了满足队列的 FIFO 的特性,我们需要用到两个栈,用它们其中一个来进行入队操作,用另一个来进行出队操作。
//@author:程序员小吴
class MyQueue {
private Stack<Integer> in = new Stack<>(), out = new Stack<>();
//定义一个辅助函数来处理当 out 为空时,将 in 里面的数据挪到 out 中去
private void transferIfEmpty() {
if (out.empty()){
while (!in.empty()){
out.push(in.pop());
}
}
}
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
in.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
transferIfEmpty();
return out.pop();
}
/** Get the front element. */
public int peek() {
transferIfEmpty();
return out.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return in.empty() && out.empty();
}
}
代码实现中涉及到多个函数,每个函数的复杂度是有所区别的。
push操作
pop操作
peek操作
empty操作
栈、队列