代码随想录打卡第10天:232. 用栈实现队列 225. 用队列实现栈

232. 用栈实现队列

题目链接:

https://leetcode.cn/problems/implement-queue-using-stacks/

思路:

准备两个栈,一个作为入栈,一个作为出栈。

入栈只存放新增的元素

出栈负责弹窗队首元素。

push操作:把所有的元素的放在入栈中,在栈顶添加元素

pop操作:把所有元素放在出栈中,在栈顶弹出元素。

empty操作:当两个栈都为空时,返回true,否则返回false

代码:

class MyQueue {

private:

stack<int> startin;

stack<int> startout;

public:

    MyQueue() {

    }

    void push(int x) {

      while(!startout.empty())

      {

          int val = startout.top();

          startout.pop();

          startin.push(val);

      }

        startin.push(x); 

    }


    int pop() {


        while(!startin.empty())

        {

            int val = startin.top();

            startin.pop();

            startout.push(val);

        }

        if(startout.empty())

            return -1;

        int top = startout.top();

        startout.pop();

        return top;

    }


    int peek() {

        int val = pop();

        startout.push(val);

        return val;

    }


    bool empty() {

        if(!startin.empty()||!startout.empty())

            return false;

        else

            return true;

    }

};

/**

* 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();

*/

225. 用队列实现栈

题目链接:

https://leetcode.cn/problems/implement-stack-using-queues/

思路:和用栈实现队列不通,这题队列2是作为队列1的备份使用。

优化:可以用一个队列实现栈。要弹出栈顶元素,只要把队列首元素放到队尾,取到最后一个即可。

class MyStack {

queue<int> qin;

queue<int> qout;

int size;

public:

    MyStack() {

        size = 0;

    }


    void push(int x) {

        qin.push(x);

        cout<<"size:"<<size<<endl;

        size++;

    }


    int pop() {

        cout<<"in pop"<<endl;

        int new_size = size;

        new_size--;

        while(new_size!=0)

        {

            int front = qin.front();

            cout<<"front:"<<front<<endl;

            qout.push(front);

            qin.pop();

            new_size--;

        }

        int top = qin.front();

        qin.pop();

        while(!qout.empty())

        {

            int front = qout.front();

            qin.push(front);

            qout.pop();

        }

        size--;

        cout<<"size:"<<size<<endl;

        return top;

    }


    int top() {

        cout<<"int top"<<endl;

        int new_size = size;

        new_size--;

        while(new_size!=0)

        {

            int front = qin.front();

            cout<<"front:"<<front<<endl;

            qout.push(front);

            qin.pop();

            new_size--;


        }

        int top = qin.front();

        qin.pop();

        cout<<"top:"<<top<<endl;

        // qin.pop();

        qout.push(top);

        cout<<"====reset===="<<endl;

        while(!qout.empty())

        {

            int front = qout.front();

            cout<<"front:"<<front<<endl;

            qin.push(front);

            qout.pop();

        }

        cout<<"qin.size"<<qin.size()<<endl;

        cout<<"qin.front"<<qin.front()<<endl;

        cout<<"qin.back"<<qin.back()<<endl;

        return top;


    }


    bool empty() {

        if(qin.empty())

            return true;

        else

            return false;

    }

};

/**

* 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();

*/

优化版本:

class MyStack {

public:

    queue<int> queue1;

    queue<int> queue2;

    MyStack() {

    }


    void push(int x) {

        queue1.push(x);

    }


    int pop() {

        int size = queue1.size();

        size--;

        while(size>0)

        {

            queue1.push(queue1.front());

            queue1.pop();

            size--;

        }

        int top = queue1.front();

        queue1.pop();

        return  top;

    }


    int top() {

        int top = pop();

        queue1.push(top);

        return top;

    }


    bool empty() {

        if(queue1.empty())

            return true;

        else

            return false;

    }

};

/**

* 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();

*/

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容