【数据结构】用两个栈实现队列

惯例。看题：

题目：用两个栈实现一个队列。队列的声明如下。请实现它的两个函数appendTail和deleteHead，分别完成对也尾部插入节点和队列头部删除节点的功能。

队列结构：

template<typenameT>classCQueue
{
public:
CQueue(void);
~CQueue(void);

voidappendTail(constT&node);
TdeleteHead();
private:
stack<T>stack1;
stack<T>stack2;
};

首先我们从题目所给出的内容上来进行思考，题目中提到了队列和栈的相关概念

那么队列的特点是先进先出（FIFO[first in first out]）,栈的特点是先进后出(FILO(first in last out)).

这个题要求的无非就是改变栈尾插和头删的进出方式。

我们完全可以想象为2个累叠的积木块来模拟2个栈。然后我们如何实现队列的先进后出呢？

其实2个栈就想到于2个容器。当栈1存储数据进行插入的时候。栈1出栈到栈2时候，就想分层的鸡尾酒进行倾倒。就可以将原本置于栈顶的数据放到栈2的栈尾。然后在进行出栈就完成了队列的先进先出的概念。

我们可以画图来看一下所需要了解的意思：

一个存储放入，一个存储删除。

大概思路就是这样,我们来看一下实现代码：

templete<typenameT>
voidCQueue<T>::appendTail(constT&element)
{
stack1.push(element);
}

templete<typenameT>
voidCQueue<T>::deleteHead()
{
if(stack2.size()<=0)
{
while(stack1.size()>0)
{
T&data=stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size()==0)
{
cout<<"queueisempty"<<endl;
}
Thead=stack2.top();
stack2.pop();

returnhead;
}

这个就是2个栈实现一个队列的题目。是不是十分简单呢

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!