算法第10天|232.用栈实现队列225. 用队列实现栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法第10天|232.用栈实现队列225. 用队列实现栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

232.用栈实现队列

力扣链接

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好。

但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部出栈，然后全部导入进输出栈（注意是全部导入），再从出栈栈顶弹出数据；如果输出栈不为空，则直接从出栈弹出数据就可以了。

我们用C++容器中的stack来作为栈的实现。其常用接口如下：

构造函数：

stack<T> stk; //stack采用模板类实现，stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数

赋值操作：

stack& operator=(const stack &stk); //重载等号操作符

数据存取：

        push(elem); //向栈顶添加元素，注意无返回值
        pop(); //从栈顶移除第一个元素，注意无返回值
        top(); //返回栈顶元素
大小操作：

empty(); //判断堆栈是否为空
size(); //返回栈的大小

class MyQueue {
private:
    stack<int> stack_in;  //输入栈，用于入队
    stack<int> stack_out;  //输出栈，用书出队
    int size;  //维护了一个size表示队列长度
public:
    MyQueue() {
        size=0;
    }
    
    void push(int x) {
        stack_in.push(x);
        size++;
    }
    
    int pop() {
        //如果输出栈为空，则先将输入栈的数据全部依次出栈，并入栈到输入栈
        if(stack_out.empty())
        {
            while(!stack_in.empty())
            {
                stack_out.push(stack_in.top());
                stack_in.pop();
            }

        }
        int tmp = stack_out.top();  //记录栈顶的值作为出队数据
        stack_out.pop();
        size--;
        return tmp;

    }
    
    int peek() {  //获取队头数据，不能删除，
        if(!stack_out.empty())
        {
            return stack_out.top();//用来读取栈顶元素，而不是出栈     
        }
        else{
            while(!stack_in.empty())
            {
                int tmp = stack_in.top();
                stack_out.push(tmp);
                stack_in.pop();
            }
            return stack_out.top();
        }

    }
    
    bool empty() {
        if(size>0)
        {
            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();
 */

如果不想维护队列的size属性，则empty()函数实现如下：

bool empty()
{
    return stack_in.empty() && stack_out.empty();
}

如果接的peek（）函数还要在判断输出栈是否为空，比较复杂，可以使用上面实现好的pop函数，也提高了代码的复用率。代码如下：

int peek()
{
    int tmp = this->pop(); //用tmp记录出队元素，也就是队首元素。本质是stack_out出栈了栈顶元素
    stack_out.push(tmp); //所以还要再给stack_out入栈回去
    return tmp;
}

225. 用队列实现栈

力扣链接

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

思路分析：

队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

所以用栈实现队列，和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。

但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后出队最后面的元素，再把其他元素从que2导回que1。

我们用c++容器中的单向queue来作为两个队列的基本实现，如果是双端队列deque没啥意义，因为两端都能出队入队，一端进，另一端出，直接就能当栈使用。

queue的常用接口如下：

构造函数：

queue<T> que; //queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que); //拷贝构造函数
赋值操作：

queue& operator=(const queue &que); //重载等号操作符
数据存取：

        push(elem); //往队尾添加元素，入队操作，无返回值。
        pop(); //从队头移除第一个元素，出队操作，无返回值。出队的元素不会被返回
        back(); //返回最后一个元素
        front(); //返回第一个元素
大小操作：

empty(); //判断堆栈是否为空
size(); //返回栈的大小
代码实现：

class MyStack {
private:
    queue<int> que1;
    queue<int> que2;//做备份用
public:
    MyStack() {
    }
    
    void push(int x) {
        que1.push(x); //入队
    }
    
    int pop() {
        //需要que1中除最后一个元素之外的所有元素出队，然后入队到que2中，这时候que1中还剩的最后一个就是该出栈的元素。
        int size = que1.size();
        while(size>1)
        {
            que2.push(que1.front());
            que1.pop();//出队
            size--;
        }
        int res = que1.front();  //记录这最后一个元素
        que1.pop();

        //然后再将que2中的元素按顺序入队到que1中，由两种思路
        //方法1.
        while(!que2.empty())
        {
            que1.push(que2.front());
            que2.pop();

        }
        //方法2
        /*que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
               que2.pop();
        }*/

        return res;

    }
    
    int top() {
        //方法1.利用刚刚实现的pop简化代码
        int tmp = this->pop();
        this->que1.push(tmp);
        return tmp;

        //方法2.或者用back（） 返回队尾元素
        //return que1.back();

    }
    
    bool empty() {
        return que1.empty();
    }
};

优化：

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。代码如下着重看一下pop（）函数：文章来源地址https://www.toymoban.com/news/detail-836901.html

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {

    }
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que.size();
       
        while (size>1) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    /** Get the top element. */
    int top() {
        return que.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};

到了这里，关于算法第10天|232.用栈实现队列225. 用队列实现栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！