ep7_9.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:2k
- /*7.9 用单链表类来表示一个双端队列,要求可在表的两端插入(链表头和尾,
- 即可用向前和也可用向后生成),但只能在表的一端删除(链表头)。给出基于
- 此结构队列的两个入队和一个出队算法的成员函数。*/
- #include<iostream>
- #include<cassert>
- using namespace std;
- template<typename T>class Queue;
- template<typename T>class Node{
- T info;
- Node<T> *link;
- public:
- Node(){link=NULL;}
- Node(T data,Node *l=NULL);
- friend class Queue<T>;
- };
- template<typename T> Node<T>::Node(T data,Node *l){
- info=data;
- link=l;
- };
- template<typename T>class Queue{
- Node<T> *front,*rear;
- public:
- Queue(){rear=front=NULL;} //构造一个空链队
- ~Queue();
- bool IsEmpty(){ return front==NULL;} //队空否?
- void EnQue(const T &); //进队
- T DeQue(); //出队
- T GetFront(); //查看队头数据
- void MakeEmpty(); //置空队列,与析构逻辑上不同,物理上一样
- void EnQueFront(const T &); //从队头入队
- };
- template<typename T>void Queue<T>::MakeEmpty(){
- Node<T> *temp;
- while(front!=NULL){
- temp=front;front=front->link;delete temp;
- }
- }
- template<typename T>Queue<T>::~Queue(){MakeEmpty();}
- template<typename T>void Queue<T>::EnQue(const T &data){
- if(front==NULL) front=rear=new Node<T>(data,NULL);
- else rear=rear->link=new Node<T>(data,NULL);
- }
- template<typename T>void Queue<T>::EnQueFront(const T &data){//从队头入队
- Node<T> *p=new Node<T>(data,NULL);
- if(front==NULL) front=rear=p;
- else{
- p->link=front;
- front=p;
- }
- }
- template<typename T>T Queue<T>::DeQue(){
- assert(!IsEmpty());
- Node<T> *temp=front;
- T data=temp->info;
- front=front->link;
- delete temp;
- return data;
- }
- template<typename T>T Queue<T>::GetFront(){
- assert(!IsEmpty());
- return front->info;
- }
- int main(){
- int i;
- Queue<char> que;
- char str1[]="abcdefghijklmnop";// 18元素数组,17个字符,再加串结束符
- for(i=0;i<17;i++) que.EnQue(str1[i]);
- for(i=0;i<17;i++) que.EnQueFront(str1[i]);
- while(!que.IsEmpty()) cout<<que.DeQue(); //先进先出,串结束符成为空格放最前面
- cout<<endl;
- if(que.IsEmpty()) cout<<"队空"<<endl;
- return 0;
- }