数据结构队列实现抽象数据类型

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 typedef struct QNode{
  5     int data;
  6     struct QNode *next;
  7 }QNode,*QueuePtr;
  8 
  9 typedef struct
 10 {
 11     QueuePtr front;
 12     QueuePtr tear;
 13 }LinkQueue;
 14 
 15 bool InitQueue(LinkQueue &Q)
 16 {
 17     Q.front = Q.tear = (QueuePtr)malloc(sizeof(QNode));
 18     if(!Q.front) exit(-1);
 19     Q.front->next = NULL;
 20     return 1;
 21 }
 22 
 23 bool Enqueue(LinkQueue &Q,int e)
 24 {
 25     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
 26     if(!p) exit(-1);
 27     p->data = e;
 28     p->next = NULL;
 29     
 30     (Q.tear)->next = p;
 31     Q.tear = p;
 32     return 1;
 33 }
 34 
 35 bool Dequeue(LinkQueue &Q,int &e)
 36 {
 37     if(Q.front == Q.tear) return 0;
 38     QNode *p = (QueuePtr)malloc(sizeof(QNode));
 39     p = Q.front->next;
 40     e = p->data;
 41     Q.front->next = p->next;
 42     if(Q.tear == p) Q.tear = Q.front;
 43     free(p);
 44     return 1;
 45 }
 46 
 47 bool GetHead(LinkQueue &Q,int &e)
 48 {
 49     if(Q.front == Q.tear) return 0;
 50     else{
 51         e = (Q.front->next)->data;
 52         return 1;
 53     }
 54 }
 55 
 56 bool Qempty(LinkQueue &Q)
 57 {
 58     if(Q.front == Q.tear) return 1;
 59     return 0;
 60 }
 61 
 62 int Length(LinkQueue &Q)
 63 {
 64     int cnt = 0;
 65     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
 66     p = Q.front;
 67     while(Q.tear != p)
 68     {
 69         cnt++;
 70         p = p->next;
 71     }
 72     return cnt;
 73 }
 74 
 75 void TraverQueue(LinkQueue &Q)
 76 {
 77     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
 78     p = Q.front;
 79     while(Q.tear != p)
 80     {
 81         p = p->next;
 82         cout << p->data << " ";
 83     }
 84     puts("");
 85 }
 86 
 87 bool DestroyQueue(LinkQueue &Q)
 88 {
 89     while(Q.front)
 90     {
 91         Q.tear = Q.front->next;
 92         free(Q.front);
 93         Q.front = Q.tear;
 94     }
 95     return 1;
 96 }
 97 
 98 bool ClearQueue(LinkQueue &Q)//这个和销毁的区别就是保留头结点 
 99 {
100     QueuePtr p,q;
101     Q.tear = Q.front;
102     p = Q.front->next;//这里保留了头结点 
103     Q.front->next = NULL;
104     
105     while(p)
106     {
107         q = p;
108         p = p->next;
109         free(q);
110     }
111     return 1;
112 }
113  
114 int main()
115 {
116     LinkQueue Q;
117     InitQueue(Q);
118     for(int i = 1;i <= 5;i++)
119     {
120         Enqueue(Q,i);
121     } 
122     cout << Length(Q) << endl;
123     TraverQueue(Q);
124     bool ok = Enqueue(Q,6);
125     if(ok)
126     TraverQueue(Q);
127     int x;
128     ok = GetHead(Q,x);
129     if(ok)
130     {
131         cout << "x = " << x << endl;
132     }
133     DestroyQueue(Q);
134     TraverQueue(Q);
135     return 0;
136 }