C語言數據結構之鏈隊列的基本操作
1.隊列的定義
隊列 (Queue)是另一種限定性的線性表,它隻允許在表的一端插入元素,而在另一端刪除元素,所以隊列具有先進先出(Fist In Fist Out,縮寫為FIFO)的特性。在隊列中,允許插入的一端叫做隊尾(rear),允許刪除的一端則稱為隊頭(front)。 假設隊列為q=(a1,a2,…,an),那麼a1就是隊頭元素,an則是隊尾元素。隊列中的元素是按照a1、a2、…、an的順序進入的, 退出隊列也必須按照同樣的次序依次出隊,也就是說,隻有在a1、a2、…、an-1都離開隊列之後,an才能退出隊列。
2.隊列的表示和實現
鏈隊列可以定義如下:
#define TRUE 1 #define FALSE 0 typedef struct QNode{ QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue;
(1) 初始化操作
Status InitQueue(LinkQueue &Q) { Q.front = Q.rear = (Queueptr) malloc(sizeof(QNode)); if(!Q.front) exit ( OVERFLOW); Q.front ->next = NULL; return OK; }
(2)銷毀隊列
Status DestroyQueue(LinkQueue &Q) { while(Q.front) { Q.rear = Q.front->next; free (Q.front); Q.front = Q.rear; } return OK; }
(3) 入隊操作
Status EnQueue (LinkQueue &Q, QelemType e) { p= (QueuePtr) malloc(sizeof(QNode)); if (!p) exit ( OVERFLOW); p->data = e; p->next = NULL; Q.rear -> next =p; Q.rear = p; return OK; }
(4) 出隊操作
Status DeQueue (LinkQueue &Q, QelemType &e) { if ( Q.front == Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next =p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK; }
附錄完整代碼:
#include<iostream> using namespace std; #define OK 1 #define FALSE 0 typedef int QElemType; typedef int Status; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr font; QueuePtr near; }LinkQueue; Status InitQueue(LinkQueue &Q) { Q.font=(QueuePtr)malloc(sizeof(QNode)); if(!Q.font) exit(FALSE); Q.font->next=NULL; Q.near=Q.font; return OK; } Status QueueEmpty(LinkQueue Q) { if(Q.font->next) return OK; return FALSE; } Status EnQueue(LinkQueue &Q,QElemType e) { QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); p->data=e; Q.near->next = p; Q.near = Q.near->next; p->next = NULL; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e) { if(!Q.font->next) return FALSE; QueuePtr p; p=Q.font->next; e=p->data; Q.font->next=p->next; if(Q.near==p) Q.near=Q.font; //當是最後一個元素時,Q.font=NULL,Q.near=Q.font free(p); return OK; } Status ClearQueue(LinkQueue &Q) { QueuePtr p; p=Q.font->next; QueuePtr q; while(p) { q=p; p=p->next; Q.font->next=p; free(q); } Q.near=Q.font; return OK; } void menu() { cout<<"初始化隊列:1"<<endl; cout<<"入隊:2"<<endl; cout<<"出隊:3"<<endl; cout<<"清空隊列:4"<<endl; cout<<"退出:5"<<endl; } int main() { LinkQueue Q; while(true) { int n; menu(); scanf("%d",&n); int e=-1; switch(n) { case 1: InitQueue(Q); continue; case 2: printf("請輸入一個元素"); scanf("%d",&e); EnQueue(Q,e); continue; case 3: DeQueue(Q,e); printf("\n出隊元素%d\n",e); continue; case 4: ClearQueue(Q); printf("清空成功\n"); continue; default: break; } if(n==5)break; } }
總結
本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!