文章目錄

• • 1.隊列的簡介
  • 2.隊列的簡單實現(xiàn)
  • 3.循環(huán)隊列說明
  • 4.循環(huán)隊列實現(xiàn)

1.隊列的簡介

隊列（Queue），簡稱隊，它也是一種運算受限的特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列的數(shù)據(jù)元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO）線性表。
對應我們?nèi)粘Ｉ钪械那樾?#xff0c;比如，在食堂的單窗口買飯，一個食堂阿姨每次只能給一位同學打飯，那么我們就需要排隊買飯，先到的同學排在隊伍的前面，后來的同學排在后面。前面的同學先買到飯然后出隊離開；后面來的同學原則上只能排到隊伍的后面（手動狗頭）。這就是先來的先請求得到服務。再比如我們有一臺網(wǎng)絡共享打印機，網(wǎng)絡中的任何一臺機器都可以向它發(fā)出打印請求。但它每次只能服務一個，該如何處理這些請求呢？這個時候控制打印機的程序就會把請求們加入到一個隊列，只要隊列中有內(nèi)容，打印機就會從不斷地從隊列頭部取出請求執(zhí)行打印。計算機的處理器也是一個共享的資源，很多程序或者說進程需要處理器的時間片來執(zhí)行，那么這些進程也會被放入一個隊列。

對于棧，插入和刪除只能從一端進行；對于隊列，插入和刪除操作必須從不同端進行。接下來我們用兩種方式來實現(xiàn)相關操作。

2.隊列的簡單實現(xiàn)

首先創(chuàng)建一個包含整型元素的數(shù)組來存儲隊列。下面是一種極其簡單的實現(xiàn)方式。代碼：

#include<stdio.h> #define MAXSIZE 10 int A[MAXSIZE];//定義一個全局整型數(shù)組存放隊元素 int front = -1; int rear = -1; //隊空時將索引置為-1； //入隊操作void Enqueue(int x){//隊滿則不支持入隊if(rear ==MAXSIZE-1){printf("Error:Queue is Full ");return ;}A[++rear] = x;}//出隊操作void Dequeue(){if((rear ==-1)&& front ==-1){printf("Error:Queue is Empty");return ;}else if(rear == front&&(rear!=-1)){//隊列只有一個元素 rear = -1;front = -1;}else{front = front+1;} } // 返回隊尾值int Rear(){return A[rear];} void Print(){int i;printf("queue: ");for(i=front+1;i<=rear;i++){printf("%d ",A[i]);}printf("\n");}int main(){Enqueue(1);Enqueue(2);Enqueue(3);Print();Dequeue();Dequeue();printf("now the queue is: ");Print();}

運行結(jié)果：

3.循環(huán)隊列說明

很明顯，以上的方法，我們只是利用簡單的數(shù)組進行了模擬。它存在著很多的不足。比如，當我們刪去隊列中的元素時，我們沒法使用他們留下來的空位，每一次Dequeue空下來的front位都會被閑置。這樣對空間造成了很大的浪費。于是，我們設計循環(huán)數(shù)組。通過取余的操作，使front和rear指針發(fā)生改變。除此之外，我們說隊列也是一種線性表，對于線性表，我們使用結(jié)構(gòu)體來定義才是一種更加理想的方式。

4.循環(huán)隊列實現(xiàn)

結(jié)構(gòu)體定義：

typedef struct {QElemType *base;//初始化動態(tài)分配的指定長度的空間int front;//頭指針，若隊列不空，指向隊列頭元素int rear;//尾指針，若隊列不空，指向隊列尾元素的下一個位置 }SqQueue;

循環(huán)隊列初始化：

bool InitQueue(SqQueue *Q) {Q->base=(QElemType*)malloc(maxQueueSize*sizeof(QElemType));if (!Q->base){return false;}Q->front=0;Q->rear=0;return true; }

入隊函數(shù)：

bool EnQueue(SqQueue *Q,QElemType e) {if ((Q->rear+1)%maxQueueSize==Q->front)//隊列滿{return false;}Q->base[Q->rear]=e;Q->rear=(Q->rear+1)%maxQueueSize;printf("%d successfully in\n",e);return true; }

出隊函數(shù)：

bool DeQueue(SqQueue *Q,QElemType *e) {if (Q->front==Q->rear)//隊列空{return false;}*e=Q->base[Q->front];Q->front=(Q->front+1)%maxQueueSize;printf("%d successfully out！\n",*e);return true; }

打印函數(shù)和主函數(shù)：

void printfQueue(SqQueue Q) {printf("Now the queue is:\n");while (Q.front!=Q.rear){if (Q.front==maxQueueSize &&(Q.rear+1)%maxQueueSize!=Q.front){Q.front=0;}printf("%d ",Q.base[Q.front]);Q.front++;}printf("\n"); }int main() {SqQueue *Q=(SqQueue*)malloc(sizeof(SqQueue));InitQueue(Q);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,1);EnQueue(Q,4);printfQueue(*Q);QElemType *e=(QElemType*)malloc(sizeof(QElemType));DeQueue(Q,e);DeQueue(Q,e);EnQueue(Q,9);EnQueue(Q,9);printfQueue(*Q);return 0; }

執(zhí)行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的C语言队列的基本实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。