[medium]用栈实现队列

难度: 中等 标题:用栈实现队列

正如标题所述,你需要使用两个栈来实现队列的一些操作。

队列应支持push(element),pop() 和 top(),其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。

思路

两个栈,stack1与stack2.stack2中元素顺序和入栈顺序完全相反。每次插入时把stack2里所有数据插入到stack1,然后插入元素到stack1末尾,再倒回stack2.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Queue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;

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

public void push(int element) {
if (stack2.empty()){
stack2.push(element);
} else {
while (!stack2.empty()){
stack1.push(stack2.pop());
}
stack1.push(element);
while (!stack1.empty()){
stack2.push(stack1.pop());
}
}
}

public int pop() {
return stack2.pop();
}

public int top() {
return stack2.peek();
}
}

链接

http://www.lintcode.com/zh-cn/problem/implement-queue-by-two-stacks/

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×