用两个栈实现一个队列——7-创新互联

 用两个栈实现一个队列，并实现两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

创新互联是一家集网站建设,溆浦企业网站建设,溆浦品牌网站建设,网站定制,溆浦网站建设报价,网络营销,网络优化,溆浦网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

  栈的特点是“先进后出，后进先出”，而队列的特点是“先进先出，后进后出”，因此可以想到只用一个栈是无法完成的，所以会需要两个栈，先将输入的数据都依次放入一个栈stack1中，但是先进去的数据会被压在栈底，而栈底的数据是需要最先被取出的，可画图如下：

当要完成在队列头部删除结点这就要用到另外一个栈stack2了，可以将第一个栈stack1的栈顶元素依次取出放进另外的栈stack2中，这样stack1中的栈底元素就变成了stack2中的栈顶元素，当需要删除队列头部结点的时候就可以pop出stack2的栈顶元素；

而需要在队列尾部插入结点就往stack1中压入数据：

也就是相当于，当stack2不为空的时候，要删除队列头部的结点就从stack2的栈顶中取出数据，如果stack2为空的时候就将stack1中的数据全部都从栈顶取出依次放入stack2中，然后再取出stack2的栈顶元素；而要在队列尾部插入结点的时候就直接往stack1里面push数据，这并不影响删除队列首部的结点，因为每次push数据都往stack1里面放，而当stack2不为空的时候从stack2中pop数据，二者并不影响；

程序如下：

#include 
#include 
using namespace std;

template 
class Queue
{
private:
    vector _stack1;         //定义队列的成员变量直接使用库类vector
    vector _stack2;
    
public:
    Queue()        //直接用类的默认构造函数，这里会自动调用库vector中的构造函数创建两个栈
    {}  

    //当需要向队列尾部放数据的时候，直接在栈1中push数据就可以了
    void appendTail(T data)
    {   
        _stack1.push_back(data);
    }   

    //当要删除队列头部的数据的时候
    void deleteHead()
    {   
        //先要判断栈2中是否有数据，如果有就直接取出栈顶的元素，此时就为队首的数据
        if(!_stack2.empty())
        {
            _stack2.pop_back();
        }
        else//若栈2为空，则需要将栈1中的数据调换到栈2中，以保证先进栈1的数据放在栈2的顶部
        {
            while(!_stack1.empty())
            {
                _stack2.push_back(_stack1.back());
                _stack1.pop_back();
            }
            if(!_stack2.empty())
                _stack2.pop_back();
            else
            {
                cout<<"the queue is empty..."< tmp1(_stack1);
        vector tmp2(_stack2);

        cout<<"head ";
        if(tmp2.empty())//当栈2为空的时候需要将栈1的数据挪到栈2再取出
        {
            while(!tmp1.empty())
            {
                tmp2.push_back(tmp1.back());
                tmp1.pop_back();
            }
            while(!tmp2.empty())
            {
                cout< queue;
    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');
    queue.appendTail('d');
    queue.appendTail('e');
    queue.print_queue();

    queue.deleteHead();
    queue.deleteHead();
    queue.print_queue();

    queue.appendTail('f');
    queue.appendTail('g');
    queue.appendTail('h');
    queue.print_queue();

    return 0;
}

因为上面的队类是模板类，因此实现了代码复用，队中的数据可以为任意类型；

运行程序：

《完》

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

网站栏目：用两个栈实现一个队列——7-创新互联
转载源于：http://dzwzjz.com/article/cejdgo.html