题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
1
2
3
4
5
|
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
|
解释：
1
2
3
4
5
6
|
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
|
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这题比较简单，主要是实现队列的基本功能，即先进先出。而我们知道栈是先进后出的，这就需要我们额外的操作了。
题目提示的比较明显，使用两个栈来实现。我们可以做出如下模型：
- 两个栈分别为输入栈和输出栈
- 输入栈负责接收 push 的内容
- 输出栈负责 pop 和 peek 的内容
- 当执行 pop 或者 peek 时，当输出栈为空时，将输入栈的内容输出到输入栈中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
in : []
out: []
--push(1)
in : [1]
out: []
--push(2)
in : [2,1]
out: []
--peek
in : []
out: [1,2]
peek = 1
--pop
in : []
out: [2]
pop = 1
--isEmpty
isEmpty(in) && isEmpty(out)
|
代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
// MyQueue 队列
type MyQueue struct {
in Stack
out Stack
}
// Constructor MyQueue构造方法
func Constructor() MyQueue {
in := new(Stack)
out := new(Stack)
return MyQueue{
in: *in,
out: *out,
}
}
func (mq *MyQueue) in2out() {
for len(mq.in) > 0 {
mq.out.Push(mq.in.Pop())
}
}
// Push Push
func (mq *MyQueue) Push(x int) {
mq.in.Push(x)
}
// Pop Pop
func (mq *MyQueue) Pop() int {
if mq.out.Len() == 0 {
mq.in2out()
}
return mq.out.Pop()
}
// Peek Peek
func (mq *MyQueue) Peek() int {
if mq.out.Len() == 0 {
mq.in2out()
}
return mq.out.Top()
}
// Empty Empty
func (mq *MyQueue) Empty() bool {
return mq.in.IsEmpty() && mq.out.IsEmpty()
}
// -------------------------------------------------------
// Stack 栈
type Stack []int
// Len 获取栈的长度
func (stack *Stack) Len() int {
return len(*stack)
}
// Push push
func (stack *Stack) Push(value int) {
*stack = append(*stack, value)
}
// Top 获取栈的第一个
func (stack *Stack) Top() int {
return (*stack)[len(*stack)-1]
}
// Pop 弹出最后一个
func (stack *Stack) Pop() int {
value := (*stack)[len(*stack)-1]
*stack = (*stack)[:len(*stack)-1]
return value
}
// IsEmpty 判断是否为空
func (stack *Stack) IsEmpty() bool {
return len(*stack) == 0
}
|
RoninZc 收录于 学习