232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.

  • int pop() Removes the element from the front of the queue and returns it.

  • int peek() Returns the element at the front of the queue.

  • boolean empty() Returns true if the queue is empty, false otherwise.
    Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

创建两个栈。
当入队列时,将元素压入第一个栈。
当出队列或进行其他操作时,如第二个栈为空,则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

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
class MyQueue {
Stack<Integer> s1;
Stack<Integer> s2;

public MyQueue() {
s1 = new Stack();
s2 = new Stack();
}

public void push(int x) {
s1.add(x);
}

public int pop() {
if (s2.isEmpty()){
while (!s1.isEmpty()){
s2.add(s1.pop());
}
return s2.pop();
}
else{
return s2.pop();
}

}

public int peek() {
if (s2.isEmpty()){
while (!s1.isEmpty()){
s2.add(s1.pop());
}
return s2.peek();
}
else{
return s2.peek();
}
}

public boolean empty() {
return s1.isEmpty() && s2.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();
*/
Author

Xander

Posted on

2022-04-12

Updated on

2022-04-11

Licensed under

Comments