//3 28.cpp
//问题描述：
//以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点
//（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
#include<iostream>
#include<cassert>
#include"队列-带头结点的链表.h"
using namespace std;
int main()
{
Queue<int> Q;
Q.Push(0);
cout<<Q.Front()<<' '<<Q.Back()<<endl;
Q.Pop();
cout<<Q.Empty()<<endl;
Q.Push(1);
Q.Push(2);
while(!Q.Empty())
{
cout<<Q.Front()<<' ';
Q.Pop();
}
cout<<"OK"<<endl;
return 0;
}
--------------------------------------------------------------------------------
//队列-带头结点的链表.h
////////////////////////////////
//基于带头结点的单链表实现
//其中的头结点指向链表尾部
template<class ElemType>
class Queue
{
struct Node //队列中结点的类型
{
ElemType data; //值域
Node* next; //指针域
};
private:
Node node;
public:
Queue()
{
node.next=NULL;
}
~Queue()
{
while(Pop());
}
public:
bool Pop()
{
if(Empty())//为空判断
return false;
if(node.next==node.next->next)//为一个结点的特化
{
delete node.next;
node.next=NULL;
return true;
}
Node* temp=node.next->next;
node.next->next=temp->next;
delete temp;//删除空间
return true;
}
void Push(const ElemType & rdata)
{
Node* temp=new Node; //新建空间
assert(temp!=NULL&&"空间分配失败");
temp->data=rdata;//拷贝内容
//接入队列
if(Empty())//对只有头结点的特化
{
node.next=temp;
temp->next=temp;
}
else
{
temp->next=node.next->next;
node.next->next=temp;
node.next=temp;
}
}
ElemType& Front()//返回队列前面元素的引用
{
return node.next->next->data;
}
ElemType& Back()//返回队列后面元素的引用
{
return node.next->data;
}
bool Empty()//判断队列是否为空
{
return node.next==NULL;
}
};
评论