剑指offer笔记（九）栈和队列

迈不过友情╰ 2022-10-09 00:33 113阅读 0赞

栈：先进后出

队列：先进先出

*  ### 用栈实现队列 ###

通过两个栈，利用先进后出的特性循环得到先进先出的特性

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

class MyQueue {
    public:
        stack<int> pushst;
        stack<int> popst;
        /** Initialize your data structure here. */
        MyQueue() {
    
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            pushst.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            int top;
            if(!popst.empty())//出队栈非空
            {
                top=popst.top();
                popst.pop();
            }
            else//出队栈为空  入队栈填入出队栈
            {
                while(!pushst.empty())
                {
                    popst.push(pushst.top());
                    pushst.pop();
                }
                top=popst.top();
                popst.pop();
            }
            return top;
        }
        
        /** Get the front element. */
        int peek() {
            int top;
            if(popst.empty())//出队栈为空
            {
                while(!pushst.empty())
                {
                    popst.push(pushst.top());
                    pushst.pop();
                }
                top=popst.top();
            }
            else//出队栈非空
                top=popst.top();
            return top;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return pushst.empty()&&popst.empty();
        }
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */

*  ### 用队列实现栈 ###

仅通过一个队列，循环进出实现栈“先进后出”

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

class MyStack {
    public:
        queue<int> q;
        /** Initialize your data structure here. */
        MyStack() {
    
        }
        
        /** Push element x onto stack. */
        void push(int x) {
            q.push(x);
        }
        
        /** Removes the element on top of the stack and returns that element. */
        int pop() {
            int n=q.size();
            while(n>1)//前n-1个先出队后入队
            {
                int front=q.front();
                q.pop();
                q.push(front);
                n--;
            }
            //n==1
            int top=q.front();
            q.pop();
            return top;
        }
        
        /** Get the top element. */
        int top() {
            return q.back();
        }
        
        /** Returns whether the stack is empty. */
        bool empty() {
            return q.empty();
        }
    };
    
    /**
     * 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();
     */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221005/b14b150d3f8e4adb840da0cb12912a01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221005/617f0e46e2a44dbb899c95b8e6def6c1.png