目錄

• 一、基礎知識
• 二、數組實現環隊
• • 2.1 初始化
  • 2.2 判斷環隊是否為空
  • 2.3 判斷環隊是否為滿
  • 2.4 入隊
  • 2.5 出隊
  • 2.6 取隊頭元素
  • 2.7 取隊尾元素
  • 2.8 銷毀環隊
• 三、鏈表實現環隊
• • 3.1 初始化
  • 3.2 判斷環隊是否為空
  • 3.3 判斷環隊是否為滿
  • 3.4 入隊
  • 3.5 出隊
  • 3.6 取隊頭元素
  • 3.7 取隊尾元素
  • 3.8 銷毀環隊

---

一、基礎知識

• 環形隊列：是首尾相連的先進后出的數據結構

• 特點：給定空間大小

• 應用：環形隊列廣泛用于網絡數據收發，和不同程序間數據交換（比如內核與應用程序大量交換數據,從硬件接收大量數據）

• 實現：① 數組環隊 ② 鏈表環隊
  

• 一個嚴重的問題：
  (1) 如何判斷隊為空？(2) 如何判斷隊為滿？答案:(1)front == tail (2)front == tail
  為了區別兩個判斷條件的重合問題，需要在數組隊/鏈隊預留一個空間的位置
  (1) front == tail (2) (tail+1)%5 == front
  

二、數組實現環隊

結構體：

typedef struct CircularQueue {int* arry; int front;int tail;int size;//數組大小 }CQueue;

2.1 初始化

//初始化 void CQueueInit(CQueue* cq, int k) {assert(cq);cq->arry = (int*)malloc(sizeof(int) * (k+1));cq->front = cq->tail = 0;cq->size = k; }

2.2 判斷環隊是否為空

//判斷環形隊列是否為空 bool CQueueIsEmpty(CQueue* cq) {assert(cq);return cq->front == cq->tail; }

2.3 判斷環隊是否為滿

//判斷環形隊列是否為滿 bool CQueueIsFull(CQueue* cq) {assert(cq);return (cq->tail + 1) % (cq->size + 1) == cq->front; }

2.4 入隊

//入隊 void CQueuePush(CQueue* cq, int x) {assert(cq);if (CQueueIsFull(cq)){printf("隊滿！");exit(0);}cq->arry[cq->tail] = x;//賦值cq->tail = (cq->tail + 1) % (cq->size + 1);//tail走一步 }

2.5 出隊

//出隊 void CQueuePop(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}cq->front = (cq->front + 1) % (cq->size + 1);//front走一步 }

2.6 取隊頭元素

//取隊頭元素 int CQueueFront(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}return cq->arry[cq->front]; }

2.7 取隊尾元素

//取隊尾元素 int CQueueBack(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}int tail_i = (cq->tail + cq->size) % (cq->size + 1);//找到tail的上一個位置return cq->arry[tail_i]; }

2.8 銷毀環隊

//環形隊列的銷毀 void CQueueDestroy(CQueue* cq) {assert(cq);free(cq->arry);free(cq); }

“向后走”：(cur+1)%(k+1)
“向前走”：(cur+k)%(k+1)

三、鏈表實現環隊

結構體：

typedef int DataType; typedef struct CQueueNode {DataType data;CQueueNode* next; }CQueueNode; typedef struct CQueue {CQueueNode* front;CQueueNode* tail; }CQueue;

3.1 初始化

//初始化 void CQueueInit(CQueue* cq, int k) {assert(cq);CQueueNode* plist = CreatCQueueList(k + 1);cq->front = cq->tail = plist; } //創建k個結點的鏈表 CQueueNode* CreatCQueueList(int k) {CQueueNode* phead = NULL;CQueueNode* tail = phead;while (k){CQueueNode* newNode = (CQueueNode*)malloc(sizeof(CQueueNode));newNode->next = NULL;if (phead == NULL){phead = tail =newNode;}else{tail->next = newNode;tail = newNode;}--k;}tail->next = phead;return phead; }

3.2 判斷環隊是否為空

//判斷環形隊列是否為空 bool CQueueIsEmpty(CQueue* cq) {assert(cq);return cq->front == cq->tail; }

3.3 判斷環隊是否為滿

//判斷環形隊列是否為滿 bool CQueueIsFull(CQueue* cq) {assert(cq);return cq->front == cq->tail->next; }

3.4 入隊

//入隊 void CQueuePush(CQueue* cq, int x) {assert(cq);if (CQueueIsFull(cq)){printf("隊滿！");exit(0);}cq->tail->data = x;cq->tail = cq->tail->next; }

3.5 出隊

//出隊 void CQueuePop(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}cq->front = cq->front->next; }

3.6 取隊頭元素

//取隊頭元素 int CQueueFront(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}return cq->front->data; }

3.7 取隊尾元素

//取隊尾元素 int CQueueBack(CQueue* cq) {assert(cq);if (CQueueIsEmpty(cq)){printf("隊空！");exit(0);}CQueueNode* cur = cq->front;while (cur){if (cur->next == cq->tail)break;cur = cur->next;}return cur->data; }

3.8 銷毀環隊

//環形隊列的銷毀 void CQueueDestroy(CQueue* cq) {assert(cq);//第一層：free鏈表結點CQueueNode* cur = cq->front;while (cur){CQueueNode* next = cur->next;free(cur);cur = next;}//第二層：free front和tailfree(cq); }

總結

以上是生活随笔為你收集整理的【数据结构(C语言描述)】环形队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。