ep7_9.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:2k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /*7.9  用单链表类来表示一个双端队列,要求可在表的两端插入(链表头和尾,
  2. 即可用向前和也可用向后生成),但只能在表的一端删除(链表头)。给出基于
  3. 此结构队列的两个入队和一个出队算法的成员函数。*/
  4. #include<iostream>
  5. #include<cassert>
  6. using namespace std;
  7. template<typename T>class Queue;
  8. template<typename T>class Node{
  9. T info;
  10. Node<T> *link;
  11. public:
  12. Node(){link=NULL;}
  13. Node(T data,Node *l=NULL);
  14. friend class Queue<T>;
  15. };
  16. template<typename T> Node<T>::Node(T data,Node *l){
  17. info=data;
  18. link=l;
  19. };
  20. template<typename T>class Queue{
  21. Node<T> *front,*rear;
  22. public:
  23. Queue(){rear=front=NULL;} //构造一个空链队
  24. ~Queue();
  25. bool IsEmpty(){ return front==NULL;} //队空否?
  26. void EnQue(const T &); //进队
  27. T DeQue(); //出队
  28. T GetFront();   //查看队头数据
  29. void MakeEmpty();     //置空队列,与析构逻辑上不同,物理上一样
  30. void EnQueFront(const T &);             //从队头入队
  31. };
  32. template<typename T>void Queue<T>::MakeEmpty(){
  33. Node<T> *temp;
  34. while(front!=NULL){
  35. temp=front;front=front->link;delete temp;
  36. }
  37. }
  38. template<typename T>Queue<T>::~Queue(){MakeEmpty();}
  39. template<typename T>void Queue<T>::EnQue(const T &data){
  40. if(front==NULL) front=rear=new Node<T>(data,NULL);
  41. else rear=rear->link=new Node<T>(data,NULL);
  42. }
  43. template<typename T>void Queue<T>::EnQueFront(const T &data){//从队头入队
  44. Node<T> *p=new Node<T>(data,NULL);
  45. if(front==NULL) front=rear=p;
  46. else{
  47. p->link=front;
  48. front=p;
  49. }
  50. }
  51. template<typename T>T Queue<T>::DeQue(){
  52. assert(!IsEmpty());
  53. Node<T> *temp=front;
  54. T data=temp->info;
  55. front=front->link;
  56. delete temp;
  57. return data;
  58. }
  59. template<typename T>T Queue<T>::GetFront(){
  60. assert(!IsEmpty());
  61. return front->info;
  62. }
  63. int main(){
  64. int i;
  65. Queue<char> que;
  66. char str1[]="abcdefghijklmnop";// 18元素数组,17个字符,再加串结束符
  67. for(i=0;i<17;i++) que.EnQue(str1[i]);
  68. for(i=0;i<17;i++) que.EnQueFront(str1[i]);
  69. while(!que.IsEmpty()) cout<<que.DeQue();    //先进先出,串结束符成为空格放最前面
  70. cout<<endl;
  71. if(que.IsEmpty()) cout<<"队空"<<endl;
  72. return 0;
  73. }