两个栈实现一个队列

àì夳堔傛蜴生んèń 2022-07-24 09:05 216阅读 0赞

## 两个栈实现一个队列 – C++ ##

题目：编写一个类，用两个栈实现一个队列，支持队列基本操作(push,pop,front)

## 实现细节 ##

1、如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中数据全部压入；  
2、**如果stackPop非空，stackPush绝对不能向stackPop()中压入数据。**

--------------------

本例中队列功能描述：

push():将一个元素放入queue内。
    front():返回queue中第一个元素。
    pop()：从queue中移除一个元素，但是不返回此元素。

--------------------

## C++实现队列类源码如下 ##

class MyQueue
    {
    private:
        stack<int>* stackPush;
        stack<int>* stackPop;
    public:
        MyQueue()
        {
            stackPush = new stack<int>;
            stackPop = new stack<int>;
        }
        ~MyQueue()
        {
            delete stackPush;
            delete stackPop;
        }
        //入队
        void push(int newNum)
        {
            stackPush->push(newNum);
        }
        //从队列中移除一个元素
        void pop()
        {
            if (stackPop->empty() && stackPush->empty())
            {
                cout << "Queue is empty" << endl;
                return ;
            }
            else if (stackPop->empty())
            {
                while (!stackPush->empty())
                {
                    int data = stackPush->top();
                    stackPush->pop();
                    stackPop->push(data);
                }
            }
            stackPop->pop();
        }
        //返回队列中第一个push进来的元素
        int front()
        {
            if (stackPop->empty() && stackPush->empty())
            {
                cout << "Queue is empty" << endl;
                return -1;
            }    
            else if (stackPop->empty())
            {
                while (!stackPush->empty())
                {
                    int data = stackPush->top();
                    stackPush->pop();
                    stackPop->push(data);
                }
            }
    
            return stackPop->top();
        }
    };

--------------------

## 程序测试 ##

#include <iostream>
    #include <stack>
    
    using namespace std;
    //上述类的源码
    int main()
    {
        MyQueue q;
        q.push(123);
        q.push(233);
        q.push(234);
        q.push(345);
        q.push(456);
        q.push(567);
        q.push(678);
        q.push(789);
        cout << "fisrt elem: " << q.front() << endl;
    
        for (int i = 0; i < 8; i++)
        {
            cout << "after pop: " << endl;
            q.pop();
            cout << "fisrt elem: " << q.front() << endl;
        }
        system("pause");
    }

--------------------

程序运行结果：

fisrt elem: 123
    after pop:
    fisrt elem: 233
    after pop:
    fisrt elem: 234
    after pop:
    fisrt elem: 345
    after pop:
    fisrt elem: 456
    after pop:
    fisrt elem: 567
    after pop:
    fisrt elem: 678
    after pop:
    fisrt elem: 789
    after pop:
    Queue is empty
    fisrt elem: -1
    请按任意键继续. . .