队列和栈的互相实现

概述：1. 用队列实现栈；2. 用栈实现队列

队列: 先进先出

栈：先进后出

队列实现栈

思路

利用队列的队尾插入（push）特性，将新元素插到队尾后，再把队列中该元素之前的所有元素依次弹出并重新压入队尾，从而让新元素“沉”到队首，模拟栈顶。

1. 若队列为空，直接 push(val)（新元素即为栈顶）。
2. 若队列非空，先记录当前长度 cnt，push(val) 后再把前 cnt 个元素依次 front() + pop() + 重新 push 到队尾。
3. 经过上述操作后，新加入的元素位于队首，即等价于 push 到栈顶。
4. Pop()：直接弹出队首元素（即栈顶）。

复杂度：Push 为 O(n)（需要搬移），Pop / Empty 为 O(1)。

实现

cpp

 
class MyStack {
 
public:
    void Push(int val)
    {
        if(queueSta.empty())
        {
            queueSta.push(val);
        }
        else
        {
            int cnt = queueSta.size();
            queueSta.push(val);
            while(cnt-- > 0)
            {
                queueSta.push(queueSta.front());
                queueSta.pop();
            }
        }
    }
    
    int Pop()
    {
        int res = queueSta.front();
        queueSta.pop();
        return res;
    }
    
    bool Empty() {return queueSta.empty();};
  
private:
  queue<int> queueSta;
};

栈实现队列

思路

利用两个栈：sta1 作为“入队栈”，sta2 作为“出队栈”。

1. Push(val)：直接压入 sta1（入队只往队尾加）。
2. Pop()：
   • 若 sta2 为空，则把 sta1 中所有元素依次弹出并压入 sta2（此时栈内元素顺序反转，sta2 的栈顶即为队首）。
   • 从 sta2 弹出栈顶元素作为出队结果。
3. 这样每个元素最多被搬移一次，均摊复杂度为 O(1)。

实现

cpp

class MyQueue {
public:
  void Push(int val)
  {
      sta1.push(val);
  }
  
  int Pop()
  {
      if(sta2.empty())
      {
          while(!sta1.empty())
          {
              sta2.push(sta1.top());
              sta1.pop();
          }
      }
      
      int res = sta2.top();
      sta2.pop();
      return res;
  }
  
private:
    stack<int> sta1,sta2;
};