首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >由两个栈组成的队列(C++)

由两个栈组成的队列(C++)

作者头像
可爱见见
发布2019-09-09 15:58:28
4330
发布2019-09-09 15:58:28
举报
文章被收录于专栏:卡尼慕卡尼慕

【题目】

编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek)。

【我的代码】

头文件:MyQueue.h

#pragma once
#include <stack>
#include <iostream>
using namespace std;
class MyQueue
{
private:
    stack<int> stack_main;
    stack<int> stack_help;
public:
    //入队
    void add(int num) {
        //如果是空的情况下,就直接压入主栈
        if (stack_main.empty())
            stack_main.push(num);
        else {
            //主栈非空,说明里面有元素,需要先把里面的元素放入help栈
            while (!stack_main.empty()) {
                int temp = stack_main.top();
                stack_help.push(temp);
                stack_main.pop();
            }
            //当main栈空了以后,才放入main栈
            stack_main.push(num);
            //再把help栈里面的元素倒回来
            while (!stack_help.empty()) {
                int temp = stack_help.top();
                stack_main.push(temp);
                stack_help.pop();
            }
        }
        cout << "【入队成功】元素:" << num << endl;
    }
    //出队
    void poll() {
        //出队操作直接把main栈顶元素弹出即可
        if (stack_main.empty()) {
            cout << "Queue is empty!" << endl;
            return;
        }
        int num = stack_main.top();
        stack_main.pop();
        cout << "【出队成功】元素:" << num << endl;
    }
    //返回队头元素
    int peek() {
        //对头元素直接就是main栈栈顶元素
        if (stack_main.empty()) {
            cout << "Queue is empty!" << endl;
            return 0;
        }   
        return stack_main.top();
    }
};

主函数:main.cpp

// 由两个栈组成的队列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include "MyQueue.h"
using namespace std;
int main() {
    cout << "|-------------------------------------------------|" << endl;
    cout << "| 1. 入队                                         |" << endl;
    cout << "| 2. 出队                                         |" << endl;
    cout << "| 3. 当前对头元素                                 |" << endl;
    cout << "| 4. 退出                                         |" << endl;
    cout << "|-------------------------------------------------|" << endl;
    MyQueue myQueue;
    while (1) {
        int num;
        cin >> num;
        int min;
        switch (num)
        {
        case 1:
            cout << "请输入入队元素:";
            int number;
            cin >> number;
            myQueue.add(number);
            cout << endl;
            break;
        case 2:
            myQueue.poll();
            break;
        case 3:
            min = myQueue.peek();
            cout << "当前对头元素:" << min << endl;
            break;
        case 4:
            return 0;
        }
    }
}

【左神思路代码】

头文件:zuoshen.h

#pragma once
#include <stack>
#include <iostream>
using namespace std;
class Zuoshen
{
private:
    //push栈只对接压栈
    stack<int> stack_push;
    //pop栈只对接出栈
    stack<int> stack_pop;
public:
    //入队
    void add(int num) {
        //无论什么时候,都只压入push栈
        stack_push.push(num);
    }
    //出队
    void poll() {
        //出队只能从pop栈中出去
        if (stack_pop.empty() && stack_push.empty()) {
            cout << "Queue is empty!" << endl;
            return;
        }
        else if(stack_pop.empty()){
            //当pop栈为空时候
            while (!stack_push.empty()) {
                //把push里面的东西放入pop
                int temp = stack_push.top();
                stack_push.pop();
                stack_pop.push(temp);
            }
        }
        int num = stack_pop.top();
        stack_pop.pop();
        cout << "【出队成功】元素:" << num << endl;
    }
    //返回队头元素
    int peek() {
        //对头元素直接就是pop栈栈顶元素
        if (stack_pop.empty() && stack_push.empty()) {
            cout << "Queue is empty!" << endl;
            return;
        }
        else if (stack_pop.empty()) {
            //当pop栈为空时候
            while (!stack_push.empty()) {
                //把push里面的东西放入pop
                int temp = stack_push.top();
                stack_push.pop();
                stack_pop.push(temp);
            }
        }
        return stack_pop.top();
    }
};

【思路对比】

我的思路是在输入的时候就进行调整操作,从而add()达到O(n),但其他操作就仅仅需要针对一个main栈操作即可,都是O(1)。我的栈的分类是主次之分,次栈只是提供了一点帮助而已。

左神的思路挺高级的,他把栈分类成同等级的栈,pop栈专门面向用户弹出元素,push栈专门面向用户的输入。当pop栈非空时,弹出时仅需pop栈;当pop栈空了后,需要立刻从push栈导入数据。push栈可以理解为一个缓存,ummm挺高级,不过最坏情况下,只有push()能达到O(1),而其他方法都是O(n)。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-09-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 卡尼慕 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档