- 题目思路
使用队列结构来模拟栈，要求实现栈的四个常用函数。
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
可以使用两个队列，一个队列为data队列，一个为help队列。当压入元素num时，即执行push(x)时将数据插入到data队列的队尾。当执行pop()或者top()时，先将data队列中的元素插入到help队列中，使data队列仅剩余一个元素，将这个元素弹出即可(也就是模拟栈弹出元素)，然后再将help队列中的元素依次插入到data队列中。
- C++实现代码
class MyStack
{
public:
/** Initialize your data structure here. */
MyStack()
{
}
/** Push element x onto stack. */
void push(int x)
{
dataqueue.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop()
{
/*dataqueue中有数据 helpqueue中没有数据*/
int num = 0;
while(dataqueue.size() > 1)
{
helpqueue.push(dataqueue.front());
dataqueue.pop();
}
num = dataqueue.front();
dataqueue.pop();
/*再把数据拷贝回dataqueue*/
while(helpqueue.size() >= 1)
{
dataqueue.push(helpqueue.front());
helpqueue.pop();
}
return num;
}
/** Get the top element. */
int top()
{
/*只是获取顶端元素 但不删除顶端元素*/
int num = pop();
push(num);
return num;
}
/** Returns whether the stack is empty. */
bool empty()
{
if(dataqueue.empty() == true && helpqueue.empty() == true)
{
return true;
}
else
{
return false;
}
}
private:
queue<int> dataqueue;
queue<int> helpqueue;
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 备注
C++的STL中有queue和deque这两个队列，其中queue是队列结构，队尾插入元素，队首弹出元素。queue不允许有遍历行为。在STL中，queue的底层实现是deque，所以queue往往不被归类为容器，而被归类为容器适配器(container adapter)。
deque是双端队列，可以在队头队尾执行入队出队操作。deque像vector一样，支持随机存取，但是效率不如vector。
deque和vector的两点区别：
deque允许常数时间内对头端进行元素插入和删除操作deque没有容量的概念，因为它是动态的以分段的连续空间组合而成，随时可以增加一段新的空间并链接起来。