隊列的順序存儲與鏈式存儲c語言實現
- 2020 年 6 月 30 日
- 筆記
一. 隊列
1.隊列定義：只允許在表的一端進行插入，表的另一端進行刪除操作的線性表。
2.循環隊列：把存儲隊列的順序隊列在邏輯上視為一個環。
循環隊列狀態：
初始時：Q.front=Q.rear=0
front指針移動：Q.front=(Q.front+1)%MaxSize
rear指針移動：Q.rear=(Q.rear+1)%MaxSize
隊列長度：(Q.rear+MaxSize-Q.front)%MaxSize
隊空條件：Q.front=Q.rear
隊滿條件：Q.front=Q.rear
3.區分隊空和隊滿的三種處理
1)犧牲一個存儲單元來區分隊空和隊滿
隊滿條件：(Q.rear+1)%MaxSize=Q.front
隊空條件：Q.front=Q.rear
隊中元素個數：(Q.rear+MaxSize-Q.front)%MaxSize
2)類型中增設表示元素個數的數據成員
隊空條件：Q.front=Q.rear && Q.size=0
隊滿條件：Q.front=Q.rear && Q.size=MaxSize
3)類型中增設tag數據成員，以區分隊空還是隊滿
tag=0時，若因刪除導致Q.front=Q.rear，則為隊空
tag=1時，若因插入導致Q.front=Q.rear，則為隊滿
二. 循環隊列的順序存儲操作
1.結構描述
typedef struct Queue{ ElemType data[MaxSize]; int front,rear,size; }Queue;
2.初始化隊列
Queue InitQueue() { Queue Q; Q.front=Q.rear=Q.size=0; return Q; }
3.判斷隊列是否為空
int Queue_Empty(Queue Q) { if(Q.front==Q.rear&&Q.size==0) return TRUE; else return FALSE; }
4.判斷隊列是否為滿
int Queue_Full(Queue Q) { if(Q.front==Q.rear&&Q.size==MaxSize) return TRUE; else return FALSE; }
5.入隊
int InQueue(Queue *q) { if(Queue_Full(*q)) return FALSE; ElemType x; printf("輸入入隊元素:"); scanf("%d",&x); q->data[q->rear]=x; q->rear=(q->rear+1)%MaxSize; q->size++; return TRUE; }
6.出隊
int OutQueue(Queue *q,ElemType *x) { if(Queue_Empty(*q)) return FALSE; *x=q->data[q->front]; q->front=(q->front+1)%MaxSize; q->size--; return TRUE; }
7.完整程式碼
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define MaxSize 10 typedef int ElemType; typedef struct Queue{ ElemType data[MaxSize]; int front,rear,size; }Queue; Queue InitQueue();//初始化隊列 int Queue_Empty(Queue Q);//判斷隊列是否為空 ,用size來判斷空還是滿 int Queue_Full(Queue Q);//判斷隊列是否滿 int InQueue(Queue *q);//入隊 int OutQueue(Queue *q,ElemType *x);//出隊,並記錄出隊元素 int main() { ElemType x; Queue Q=InitQueue(); InQueue(&Q); InQueue(&Q); InQueue(&Q); InQueue(&Q); printf("此時隊列長度:%d\n",Q.size); return 0; } Queue InitQueue() { Queue Q; Q.front=Q.rear=Q.size=0; return Q; } int Queue_Empty(Queue Q) { if(Q.front==Q.rear&&Q.size==0) return TRUE; else return FALSE; } int Queue_Full(Queue Q) { if(Q.front==Q.rear&&Q.size==MaxSize) return TRUE; else return FALSE; } int InQueue(Queue *q) { if(Queue_Full(*q)) return FALSE; ElemType x; printf("輸入入隊元素:"); scanf("%d",&x); q->data[q->rear]=x; q->rear=(q->rear+1)%MaxSize; q->size++; return TRUE; } int OutQueue(Queue *q,ElemType *x) { if(Queue_Empty(*q)) return FALSE; *x=q->data[q->front]; q->front=(q->front+1)%MaxSize; q->size--; return TRUE; }
View Code
運行示例：
三. 隊列的鏈式存儲
鏈隊列：同時帶有隊頭指針和隊尾指針的單鏈表。
1.結構描述
typedef struct Node{ ElemType data; struct Node *next; }Node; typedef struct Queue{ struct Node *front,*rear; }Queue;
2.鏈隊列初始化
Queue InitQueue() { Queue Q; Q.front=Q.rear=(Node*)malloc(sizeof(Node)); Q.front->next=NULL; return Q; }
3.判斷隊列是否為空
int Queue_Empty(Queue Q) { if(Q.front==Q.rear) return TRUE; else return FALSE; }
4.入隊
void InQueue(Queue *q) { ElemType x; printf("輸入入隊元素:"); scanf("%d",&x); Node *p=(Node*)malloc(sizeof(Node)); p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; }
5.出隊
int OutQueue(Queue *q,ElemType *x) { if(Queue_Empty(*q)) { return FALSE; } Node *p=q->front->next; *x=p->data; q->front->next=p->next; if(q->rear==p) { q->rear=q->front; } free(p); return TRUE; }
6.完整程式碼
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 typedef int ElemType; typedef struct Node{ ElemType data; struct Node *next; }Node; typedef struct Queue{ struct Node *front,*rear; }Queue; Queue InitQueue();//鏈隊列初始化 int Queue_Empty(Queue Q);//判斷隊列是否為空 void InQueue(Queue *q);//入隊 int OutQueue(Queue *q,ElemType *x);//出隊 int main() { ElemType x; Queue Q=InitQueue(); InQueue(&Q); InQueue(&Q); InQueue(&Q); OutQueue(&Q,&x); printf("出隊元素:%d\n",x); return 0; } Queue InitQueue() { Queue Q; Q.front=Q.rear=(Node*)malloc(sizeof(Node)); Q.front->next=NULL; return Q; } int Queue_Empty(Queue Q) { if(Q.front==Q.rear) return TRUE; else return FALSE; } void InQueue(Queue *q) { ElemType x; printf("輸入入隊元素:"); scanf("%d",&x); Node *p=(Node*)malloc(sizeof(Node)); p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; } int OutQueue(Queue *q,ElemType *x) { if(Queue_Empty(*q)) { return FALSE; } Node *p=q->front->next; *x=p->data; q->front->next=p->next; if(q->rear==p) { q->rear=q->front; } free(p); return TRUE; }
View Code
運行示例：
