题目.用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead
分别完成在对尾插入节点和在队头删除节点。
该队列类模板如下:
template <typename T>
class CQueue
{
public:
void appendTail(const T& node);
T deleteHead() private:
stack<T> stack1;
stack<T> stack2;
11 }
首先先说明一些概念:
栈和队列是两种常用的抽象的数据结构。当然可以用数组和链表分别来实现。
1.栈的特点是先进后出，最后进入栈的元素最先出栈,而最先进入栈的元素却被
压在栈底，最后才能取出。
2.队列的特点是先进先出，类似于食堂打饭排队一样，先排队的先打饭，后
排队的后打饭。
3.这里我们声明了一个函数模板，函数模板其实是一种泛型编程思想，而
C++中的STL库大量使用这种思想，比如我们声明一个容器vector，这个
vector可以是整型的容器 vector<int> 可以是string类型的容器 vector<string>
然而vector对于不同的数据类型提供了同样的操作，这使得程序的可复用性
大大增强。
两个栈实现一个队列的插入和删除功能，步骤如下:
1.设两个栈为stack1和stack2
2.队列尾端插入直接插入在stack1中
3.对于删除队列头部节点，如果stack2不为空,
那么直接从stack2顶端取出元素(stack2中的元素为stack1中的元素顺序出栈再顺序插入到栈stack2中)
4.如果stack2为空,那么我们将stack1中的元素顺序出栈再压入stack2中。然后再从stack2中取出元素。
实现如下:
single.h中我们实现这个队列模板类:
#include <stack>
using namespace std; template <typename T>
class CQueue
{
public:
void appendTail(const T& node);
T deleteHead(); private:
stack<T> stack1;
stack<T> stack2;
}; template <typename T> void CQueue<T>::appendTail(const T& node)
{
stack1.push(node);
} template <typename T> T CQueue<T>::deleteHead()
{
if(!stack2.empty())
{
T temp=stack2.top();
stack2.pop();
return temp;
}
else
{
if(stack1.empty())
{
cout<<"队列元素为空,请先插入元素入队列\n";
}
else
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
} T temp=stack2.top();
stack2.pop();
return temp;
} }
}
在main.cpp中测试该队列类的插入和删除:
#include "single.h"
#include <iostream>
using namespace std; int main()
{
CQueue<int> queue;
int data;
queue.deleteHead();
cout<<"Please input the data you want to append in queue(0-exit):"<<endl;
while(true)
{
cin>>data;
if(data!=)
{
queue.appendTail(data);
}
else
{
break;
} } cout<<"Delete a queue node:"<<queue.deleteHead()<<endl;
cout<<"Delete a queue node:"<<queue.deleteHead()<<endl;
cout<<"Delete a queue node:"<<queue.deleteHead()<<endl;
queue.deleteHead(); return ;
}
运行截图如下：
我们再队列中依次进入1,2,3 删除时也是按照先进先出的顺序删除节点。当队列无元素时则会提醒我们队列为空。
好了，就到这里吧。是不是明白了呢?