首页 > 代码库 > 用两个栈实现一个队列 & 用两个队列实现一个栈

用两个栈实现一个队列 & 用两个队列实现一个栈

2024-07-03 13:20:16   233人阅读

队列（先进先出）和栈（先进后出）都是常用的经常讨论的基本的数据结构，本文要讨论的是一对有趣的问题：如何用两个栈（队列）实现一个队列（栈），下面将分别说明，并附示例代码。

        1、用两个栈实现一个队列

         基本思路：初始有两个空栈s1和s2，当入队列是，将元素加入s1，而出队列则从s2出，当然s1与s2之间存在一定的交互。

  • 入队：元素压入栈s1即可。
  • 出队：首先看s2是否为空，若s2为空，则依次弹出s1的元素，加入s2中；若不为空，则不需额外处理；

                         之后弹出s2中的栈顶元素（即为队列的首元素）删除即可。

  • 获得队首元素：与出队操作类似，区别只是在最后弹出s2中的栈顶元素（即为队列的首元素）并返回而不删除。

        代码实现以及简单的测试代程序如下：

/*用栈实现队列的功能：
*要用到两个栈，一个用于入队列，一个用于出队列
* by F8Master
*FileName: QueueByStack.cpp
*/

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

template<class T>
class MyQueue
{
public:
    MyQueue(){};
    ~MyQueue(){};
    void push(T &item)//队尾压入元素
    {
        s1.push(item);
    }
    void pop()//删除队首元素
    {
        if(s2.empty())//栈2为空
        {
            if(s1.size()==0)//两个栈均为空，则队列为空
            {
                cout<<"队列为空,无元素弹出"<<endl;
                return ;
            }
            while(!s1.empty())//将栈1的元素全部压入栈2中
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        s2.pop();
    }
    T front()//取队首元素
    {
        if(s2.empty())//栈2为空
        {
            if(s1.size()==0)//两个栈均为空，则队列为空
            {
                cout<<"队列为空"<<endl;
                return NULL;
            }
            while(!s1.empty())//将栈1的元素全部压入栈2中
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    int size()
    {
        return s1.size()+s2.size();
    }
private:
    stack<T> s1;
    stack<T> s2;
};

//简单的测试
void test_MyQueue()
{
    cout<<"-----Test MyQueue------"<<endl;
    MyQueue<int> mq;
    for(int i = 1;i<=10;i++)
        mq.push(i);
    cout<<"队首元素出队:";
    cout<<mq.front()<<" "<<endl;
    mq.pop();
    cout<<"此时队首元素为："<<mq.front()<<endl;

    for(int i = 11;i<=20;i++)
        mq.push(i);
    int n = mq.size();
    cout<<"队列元素依次显示并出队："<<endl;
    for(int i =0;i<n;i++)
    {
        cout<<mq.front()<<" ";
        mq.pop();
    }
}

测试截图：

1

2、两个队列实现一个栈

        基本思路：初始有两个空队列q1和q2，q1用于存储栈中元素，q2用于在pop()和top()操作时候临时存放q1的元素。

        入栈push()：将元素直接加入队列q1的尾部

        出栈pop()：先判断队列q1元素数目是否为1，若为一，直接弹出并删除即可；若多于1，则将q1中元素弹出并加入q2直至q1剩余一个元素，将其删除，然后将

                   q2暂存的元素弹出并压入q1即可。

        获得栈顶元素top():与pop()操作类似，只是对于q1中的最后一个元素，将其返回而不是删除。

        实现代码及简单的测试程序如下：

/*用队列实现栈的功能：
*要用到两个队列，队列一用于存储，队列而用于临时调整队列一以便弹出元素
* by F8Master
*/

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

template<class T>
class MyStack
{
public:
    MyStack(){};
    ~MyStack(){};
    void push(T item)//压入元素到栈顶
    {
        q1.push(item);
        //cout<<item<<" 压入栈"<<endl;
    }
    void pop()//弹出栈顶元素，但不返回
    {
        T temp;
        if(q1.size()>1)
        {    
            while(q1.size()!=1)
            {
                temp = q1.front();
                
                q2.push(temp);
                q1.pop();
            }
            q1.pop();//弹出栈顶元素
            while(!q2.empty())
            {
                temp = q2.front();
                
                q1.push(temp);
                q2.pop();
            }
            return ;
        }
        else if(q1.size()==1)
        {
            q1.pop();
            return ;
        }
        else //栈为空
        {
            cout<<"栈为空！"<<endl;
            return ;
        }
    }
    T top()//返回栈顶元素,但不删除
    {
        T temp,temp2;
        if(q1.size()>1)
        {    
            while(q1.size()!=1)
            {
                temp = q1.front();                
                q2.push(temp);
                q1.pop();
            }
            temp2 = q1.front();//此为栈顶元素，保存以留作输出
            q2.push(temp2);
            q1.pop();
            while(!q2.empty())
            {
                temp = q2.front();
                q1.push(temp);
                q2.pop();
            }
            return temp2;
        }
        else if(q1.size()==1)
        {
            return q1.front();
        }
        else //栈为空
        {
            cout<<"栈为空！"<<endl;
            return NULL;
        }
    }
    int size()
    {
        return q1.size();
    }
private:
    queue<T> q1;
    queue<T> q2;
};

//简单的测试
void test_MyStack()
{
    cout<<"-----Test MyStack------"<<endl;
    MyStack<int> ms;
    for(int i = 1;i<=10;i++)
        ms.push(i);
    cout<<"栈顶元素出栈:";
    cout<<ms.top()<<" "<<endl;;
    ms.pop();
    cout<<"此时栈顶元素为: "<<ms.top()<<endl;

    for(int i = 11;i<=20;i++)
        ms.push(i);
    int n = ms.size();
    cout<<"栈顶元素依次显示并出栈："<<endl;
    for(int i =0;i<n;i++)
    {
        cout<<ms.top()<<" ";
        ms.pop();
    }
}

测试截图：

2


联系
我们