本文共 1271 字，大约阅读时间需要 4 分钟。

Implement Queue using Stacks两个栈实现队列

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

• push(x) – 将一个元素放入队列的尾部。
• pop() – 从队列首部移除元素。
• peek() – 返回队列首部的元素。
• empty() – 返回队列是否为空。

方法1:入队O(n),出队O(1)

class MyQueue {
   public:    MyQueue() {
   }        void push(int x) {
           stack
   
     tmp;        while (!st.empty()) {
               tmp.push(st.top()); st.pop();        }        st.push(x);        while (!tmp.empty()) {
               st.push(tmp.top()); tmp.pop();        }    }        int pop() {
           int val = st.top(); st.pop();        return val;    }        int peek() {
           return st.top();    }        bool empty() {
           return st.empty();    }    private:    stack
    
      st;};
    
   

方法2:入队O(1),出队O(1) 摊还复杂度

class MyQueue {
   public:       MyQueue() {
   }        void push(int x) {
       	s1.push(x);    }        int pop() {
           shiftStack();        int val = s2.top(); s2.pop();        return val;    }        int peek() {
           shiftStack();        return s2.top();    }    bool empty() {
           return s1.empty()&&s2.empty();    }        void shiftStack() {
   //将s1的所有元素弹出到s2，再从s2中弹出。        if (!s2.empty()) return;        while (!s1.empty()) {
               s2.push(s1.top());            s1.pop();        }    }private:    stack
   
     s1,s2;};
   

转载地址：https://blog.csdn.net/weixin_42490152/article/details/100941465 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！