【数据结构】两个栈实现一个队列【面试】-创新互联

栈结构：先进后出，后进先出，只允许在栈尾操作。

创新互联公司主要从事成都网站设计、网站建设、外贸网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务龙马潭,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

队列：先进先出，在队尾入队，在队头出队。

要想用两个栈实现一个队列，就需要使用一个相当于中间量的结构进行队列的入队和出队操作。

用图形象化为：

这样问题就从图中得出了思路：

入队操作：把入队元素一一存入一个栈结构中即可。

出队操作：出队时，先判断另一个栈结构中是否有元素，若有先将元素出栈Pop（）；若为空，则把栈S1中的元素全部倒入Push（）栈S2中，然后让S2栈顶元素出栈Pop（），此时的元素序列和栈S1中刚好相反，即达到出队效果。

那么，用代码实现也变得简单：

#include <iostream>
#include <stack>
using namespace std;

class Queue
{
public:
    void Push_Queue(int val)
    {
        s1.push(val);   // 实现了入队尾入队操作
        cout <<s1.top() << " ";
    }

    void Pop_Queue()
    {
        if (s2.empty())
        {
            while (s1.top())
            {
                s2.push(s1.top()--);
            }
             s2.pop();  // 实现了队头出队操作
        }
        else
        {
            s2.pop();
        }
    }

    void Show()
    {
        cout << endl;
        // 因为使用的是系统库stack，其pop函数返回值为void，所以不能打印出来，我们只打印pop后的队头元素进行验证
        cout << s2.top() << endl; 
    }

private:
    stack<int> s1;
    stack<int> s2;

};

int main()
{
    Queue q;  // ？？构造函数的参数
    q.Push_Queue(1);
    q.Push_Queue(2);
    q.Push_Queue(3);
    q.Push_Queue(4);
    q.Push_Queue(5);

    q.Pop_Queue();

    q.Show(); // 打印pop后的对头元素

    system("pause");
    return 0;
}

如有纰漏，欢迎指正。

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

分享名称：【数据结构】两个栈实现一个队列【面试】-创新互联
网址分享：https://www.cdcxhl.com/article18/dhhpgp.html

成都网站建设公司_创新互联，为您提供手机网站建设、外贸建站、用户体验、企业网站制作、自适应网站、全网营销推广

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联