队列和栈的互相实现

文章目录

1. 队列实现栈
1. 1.1. 思路
2. 1.2. 实现
2. 栈实现队列
1. 2.1. 思路
2. 2.2. 实现

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

队列: 先进先出

栈：先进后出

队列实现栈

思路

实现


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;
};

栈实现队列

思路

实现

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;
};