用队列实现栈

LeetCode

用队列实现栈

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意:

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

首先需要明白的就是栈和队列之间的区别。这是这道题的关键，如果不明白或者不知道，那做出这道题就没有希望了。

栈每一次的push操作和pop操作都是在栈顶进行的。这也就造成了栈一种先入后出的特性，也就是最先入栈的会在最后被弹出栈。

队列就有所不同了。push操作是在队列的头部进行数据的压入，pop操作是在队列的尾部进行数据的弹出。这就是队列先入先出的原因，也就是最先入队的最先被弹出队列。

栈可以看做一条射线，底部是固定的；队列是一条直线，操作在两端进行，一端用来进入队列，一端用来出队列。

那么用队列实现栈中。最最重要的区别也就在于弹出栈和弹出队列所取的数据位置不同，一个只在一端操作，一个在另一端操作，所以每次往队列中压入一个新的数据，就要把这个数据给放到队尾，毕竟模拟栈的先入后出的模式。(对应代码即push操作)。

pop操作：队列的pop操作即推出队列尾部的数据，此时队列尾部的数据就是最新压入队列的数据(经过了上述的push操作后)，那么直接进行pop就可以了。就可以实现栈先入后出的特性。

top操作：如果是栈的话，top指的是栈顶，栈顶就是最新压入的数据。可是对于现在的队列，最新压入的数据放在了队列的尾部，所以可以使用front()函数，该函数就是用于返回尾部的数据值。

class Mystack(){
  private:
  	queue<int> q1;
  public:
  	Mystack(){}
  
  	/** Push element x onto stack. */
  	void push(int x){
      q1.push(x);
 /*增加判断，队列是否有大于1个数据存储。如果有就将先于数据x的所有数据重新压入队列，而且是每次从队尾取出一个数据*/
      for(int i = 0; i + 1 < q1.size(); i++){	
        q1.push(q1.front());
        q1.pop();
      }
    }
  	
  	/** Removes the element on top of the stack and returns that element. */
  	int pop(){
      int num = q1.front();
      q1.pop();
      return num;
    }
  
  	/** Get the top element. */
  	int top(){
      return q1.front();
    }
  	
  	 /** Returns whether the stack is empty. */
  	bool empty(){
      return q1.empty();
    }
};