C語言實現隊列與雙端隊列：數組版完整教學

編輯：關於C語言

引言

隊列是一種遵循先進先出（FIFO）原則的線性數據結構，廣泛應用於作業系統調度、網路封包處理、緩衝區管理等場景。雙端隊列則進一步允許在兩端進行插入與刪除操作，靈活性更高。本文將以 C 語言為工具，詳細展示如何使用數組實現循環隊列與雙端隊列，並提供完整的標頭檔與原始碼供參考。

一、循環隊列的實現

1.1 設計思路

為了避免數據搬移，採用循環數組策略：維護 Front（隊頭索引）、Rear（隊尾索引）、Size（當前元素數）與 Capacity（最大容量）。入隊時 Rear 後移，出隊時 Front 後移，均透過取模運算實現環狀效果。

1.2 標頭檔 `queue.h`

typedef int ElementType;
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);

#endif // QUEUE_H_INCLUDED

1.3 輔助標頭檔 `fatal.h`

#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str) FatalError(Str)
#define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED

1.4 核心實現 `queue.c`

#include "queue.h"
#include "fatal.h"

#define MinQueueSize 5

struct QueueRecord {
    int Capacity;
    int Front;  // 指向隊頭元素
    int Rear;   // 指向隊尾元素
    int Size;
    ElementType *Array;
};

int IsEmpty(Queue Q) { return Q->Size == 0; }
int IsFull(Queue Q)  { return Q->Size == Q->Capacity; }

Queue CreateQueue(int MaxElements) {
    Queue Q;
    if (MaxElements < MinQueueSize) Error("Queue size is too small");
    Q = malloc(sizeof(struct QueueRecord));
    if (Q == NULL) FatalError("Out of space!!!");
    Q->Array = malloc(sizeof(ElementType) * MaxElements);
    if (Q->Array == NULL) FatalError("Out of space!!!");
    Q->Capacity = MaxElements;
    MakeEmpty(Q);
    return Q;
}

void MakeEmpty(Queue Q) {
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}

void DisposeQueue(Queue Q) {
    if (Q != NULL) {
        free(Q->Array);
        free(Q);
    }
}

static int Succ(int Value, Queue Q) {
    if (++Value == Q->Capacity) Value = 0;
    return Value;
}

void Enqueue(ElementType X, Queue Q) {
    if (IsFull(Q)) Error("Full queue");
    else {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}

ElementType Front(Queue Q) {
    if (!IsEmpty(Q)) return Q->Array[Q->Front];
    Error("Empty queue");
    return 0;
}

void Dequeue(Queue Q) {
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
    }
}

ElementType FrontAndDequeue(Queue Q) {
    ElementType X = 0;
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        X = Q->Array[Q->Front];
        Q->Front = Succ(Q->Front, Q);
    }
    return X;
}

二、雙端隊列的實現

2.1 設計差異

雙端隊列在循環隊列基礎上新增 Push/Pop（隊頭操作）與 Inject/Eject（隊尾操作），並引入 Prev 函數實現索引前移。

2.2 標頭檔 `deque.h`

#define DEQUE_H_INCLUDED
struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
ElementType Front(Queue Q);      // 取隊頭
void Push(ElementType X, Queue Q);   // 隊頭入隊
void Pop(Queue Q);               // 隊頭出隊
ElementType FrontAndPop(Queue Q);    // 隊頭出隊並取值
ElementType Rear(Queue Q);       // 取隊尾
void Inject(ElementType X, Queue Q); // 隊尾入隊
void Eject(Queue Q);             // 隊尾出隊
ElementType RearAndEject(Queue Q);   // 隊尾出隊並取值
#endif // DEQUE_H_INCLUDED

2.3 核心實現 `deque.c`

#include "deque.h"
#include "../lib/fatal.h"

#define MinQueueSize 5

struct QueueRecord {
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};

/* IsEmpty, IsFull, CreateQueue, MakeEmpty, DisposeQueue 與 queue.c 相同 */

static int Succ(int Value, Queue Q) {
    if (++Value == Q->Capacity) Value = 0;
    return Value;
}

static int Prev(int Value, Queue Q) {
    if (--Value == -1) Value = Q->Capacity - 1;
    return Value;
}

/* 隊頭操作 */
ElementType Front(Queue Q) {
    if (!IsEmpty(Q)) return Q->Array[Q->Front];
    Error("Empty queue");
    return 0;
}

void Push(ElementType X, Queue Q) {
    if (IsFull(Q)) Error("Full queue");
    else {
        Q->Size++;
        Q->Front = Prev(Q->Front, Q);
        Q->Array[Q->Front] = X;
    }
}

void Pop(Queue Q) {
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
    }
}

ElementType FrontAndPop(Queue Q) {
    ElementType X = 0;
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        X = Q->Array[Q->Front];
        Q->Front = Succ(Q->Front, Q);
    }
    return X;
}

/* 隊尾操作 */
ElementType Rear(Queue Q) {
    if (!IsEmpty(Q)) return Q->Array[Q->Rear];
    Error("Empty queue");
    return 0;
}

void Inject(ElementType X, Queue Q) {
    if (IsFull(Q)) Error("Full queue");
    else {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}

void Eject(Queue Q) {
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        Q->Rear = Prev(Q->Rear, Q);
    }
}

ElementType RearAndEject(Queue Q) {
    ElementType X = 0;
    if (IsEmpty(Q)) Error("Empty queue");
    else {
        Q->Size--;
        X = Q->Array[Q->Rear];
        Q->Rear = Prev(Q->Rear, Q);
    }
    return X;
}