C 語言實作循環隊列（連續儲存版）

隊列抽象資料型態 (ADT)

• 先進先出 (FIFO)：只能在隊尾入隊、隊頭出隊。
• 連續儲存：以固定大小陣列實作，需處理「滿/空」判斷與索引環繞。

關鍵設計：head / tail 索引

• head 指向隊頭元素。
• tail 指向隊尾元素的下一個位置（預留一格區分滿/空）。
• 空：head == tail。滿：(tail+1)%capacity == head。有效元素數 = (tail-head+capacity)%capacity。
• 入隊：data[tail]=val; tail=(tail+1)%cap;。出隊：head=(head+1)%cap;（不需清除資料）。

完整程式碼

/*************************************************************************
> File Name: sequeue.c
> Author: Baniel Gao
> Mail: createchance@163.com
> Blog: blog.csdn.net/createchance
> Created Time: Fri 20 Dec 2013 11:57:32 AM CST
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define _DEBUG_ 1

typedef struct {
    int capacity;
    int head;
    int tail;
    int *data;
} SeqQueue;

SeqQueue *seqqueue_init(int size) {
    SeqQueue *q = malloc(sizeof(SeqQueue));
    q->capacity = size;
    q->head = q->tail = 0;
    q->data = malloc(sizeof(int) * size);
    return q;
}

int seqqueue_is_empty(SeqQueue *q) { return q->head == q->tail; }
int seqqueue_is_full(SeqQueue *q) { return (q->tail + 1) % q->capacity == q->head; }

int seqqueue_enqueue(SeqQueue *q, int val) {
    if (seqqueue_is_full(q)) return -1;
    q->data[q->tail] = val;
    q->tail = (q->tail + 1) % q->capacity;
    return 0;
}

int seqqueue_dequeue(SeqQueue *q) {
    if (seqqueue_is_empty(q)) return -1;
    q->head = (q->head + 1) % q->capacity;
    return 0;
}

void seqqueue_free(SeqQueue *q) { free(q->data); free(q); }

#if _DEBUG_
void seqqueue_debug(SeqQueue *q) {
    puts("------------------------ DEBUG ----------------------");
    printf("capacity=%d\thead=%d\ttail=%d\n", q->capacity, q->head, q->tail);
    puts("-----------------------------------------------------");
    for (int i = 0; i < q->capacity; ++i) printf("%5d", q->data[i]);
    puts("\n-----------------------------------------------------");
}
#endif

int main() {
    SeqQueue *q = seqqueue_init(10);
    int val = 100;
    while (seqqueue_enqueue(q, val++) == 0);
#if _DEBUG_
    puts("After enqueue..."); seqqueue_debug(q);
#endif
    while (seqqueue_dequeue(q) == 0);
#if _DEBUG_
    puts("After dequeue..."); seqqueue_debug(q);
#endif
    seqqueue_free(q);
    return 0;
}

除錯輸出範例

After enqueue...
capacity=10    head=0    tail=9
-----------------------------------------------------
  100  101  102  103  104  105  106  107  108  109
-----------------------------------------------------

After dequeue...
capacity=10    head=9    tail=9
-----------------------------------------------------
  100  101  102  103  104  105  106  107  108  109
-----------------------------------------------------

註：出隊後 head=9, tail=9 表示空隊列，資料仍殘留陣列中（不影響正確性）。

優化方向

• 動態擴容：滿時 realloc 並重新排列元素至索引 0 起始。
• 泛型化：用 void* 陣列 + 元素大小參數，支援任意類型。
• 執行緒安全：加入 mutex 保護 head/tail 操作。