首页 > itarticle > 40. implement queue by two stacks

40. implement queue by two stacks

admin 11月 13, 2020 0

explanation

there are two stacks: stack1 , stack2

push
directly push into stack1

pop
if !stack2.isEmpty(), return stack2.pop()
move stack 1 to stack 2
return stack1.pop()

top
if !stack2.isEmpty(), return stack2.peek();
move stack 1 to stack 2
return stack2.peek();

code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public () {

stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();

}

/*
* @param element: An integer
* @return: nothing
*/
public void push(int element) {
// write your code here
stack1.push(element);
}

/*
* @return: An integer
*/
public int pop() {
// write your code here
// 如果空的话pop？
if (!stack2.isEmpty()) {
return stack2.pop();
}

while (stack1.size() > 1) {
stack2.push(stack1.pop());
}

return stack1.pop();

}

/*
* @return: An integer
*/
public int top() {
// write your code here
if (!stack2.isEmpty()) {
return stack2.peek();
}
while (stack1.size() > 0) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
}