解题思路

方法一 双队列 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;
};