解题思路

方法一 双队列 O(1) push O(n) pop

进的时候直接进,没啥要求

出的时候需要弹出最后进入的那个元素,因此把这个元素之前的所有元素逐个弹出并放入空队列,最后弹出这个元素

这个方法对top()操作极不友好。。

方法二 双队列 O(n) push $O(1) pop

这个方法是在进的时候就构造好顺序,方便弹出

进的时候先将新元素放入空队列,再将已有队列中元素弹出,依次加入新元素所在队列

简单来说将队列前端和栈顶视为同一个方向,每次进的时候其实是在队列前端插入元素,也就是栈顶

方法三 单队列

其实上面两种方法都可以用一个队列实现

核心就是将弹出元素放入新队列的操作改为放入当前队列。。其实就是两个队列拼在一起,现有队列在前,新队列在后

代码

这里给出方法二的单队列的 C++ 实现

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
class MyStack
{
public:
/** Initialize your data structure here. */
// MyStack() {}

/** Push element x onto stack. */
void push(int x)
{
que.push(x);
for (auto i = 0; i < que.size() - 1; i++)
{
que.push(que.front());
que.pop();
}
}

/** Removes the element on top of the stack and returns that element. */
int pop()
{
const auto temp = que.front();
que.pop();
return temp;
}

/** Get the top element. */
int top()
{
return que.front();
}

/** Returns whether the stack is empty. */
bool empty()
{
return que.empty();
}

private:
queue<int> que;
};