雙棧實現隊列：C 語言完整實現與核心邏輯深度解析

編輯：關於C語言

一、核心思想：以「後進先出」模擬「先進先出」

隊列（FIFO）與棧（LIFO）操作特性相反。利用兩個棧可完美模擬隊列行為：

src 棧（入隊棧）：負責接收新元素，push 操作即入隊
dest 棧（出隊棧）：負責輸出元素，pop 操作即出隊
關鍵機制：當 dest 為空時，將 src 所有元素倒入 dest，順序自然反轉，實現 FIFO

二、棧的基礎實現（動態數組版）

typedef struct stack {
    int *a;        // 元素存儲數組
    int loc;       // 當前棧頂索引（兼作元素計數）
    int max;       // 最大容量
} Stack;

Stack* init_stack(int capacity) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->a = (int*)malloc(sizeof(int) * capacity);
    s->loc = 0;
    s->max = capacity;
    return s;
}

// 基礎操作
int is_empty(Stack* s) { return s->loc == 0; }
int is_full(Stack* s)  { return s->loc == s->max; }
int size(Stack* s)     { return s->loc; }

void push(Stack* s, int val) {
    if (is_full(s)) exit(EXIT_FAILURE);
    s->a[s->loc++] = val;
}

int pop(Stack* s) {
    if (is_empty(s)) exit(EXIT_FAILURE);
    return s->a[--s->loc];
}

int peek(Stack* s) {
    if (is_empty(s)) exit(EXIT_FAILURE);
    return s->a[s->loc - 1];
}

三、棧間元素轉移：copy 函數詳解

void transfer(Stack* src, Stack* dest) {
    // 容量檢查
    if (src->loc + dest->loc > dest->max) exit(EXIT_FAILURE);
    
    while (!is_empty(src)) {
        push(dest, pop(src));
    }
}

關鍵點：轉移過程中 src 元素順序反轉，先入 src 的元素最終位於 dest 棧頂，下次 pop 即可先出隊。

四、隊列操作封裝

// 入隊：直接 push 到 src
void enqueue(Stack* src, Stack* dest, int val) {
    if (is_full(src)) exit(EXIT_FAILURE);
    push(src, val);
}

// 出隊：優先從 dest 取，dest 空則轉移
int dequeue(Stack* src, Stack* dest) {
    if (is_empty(src) && is_empty(dest)) exit(EXIT_FAILURE);
    
    if (is_empty(dest)) transfer(src, dest);
    return pop(dest);
}

五、完整測試主程序

int main() {
    Stack* src = init_stack(3);
    Stack* dest = init_stack(3);
    
    push(src, 1); push(src, 2);
    printf("出隊: %d\n", dequeue(src, dest));  // 1
    
    push(src, 3); push(src, 4); push(src, 5);  // src滿
    printf("出隊: %d\n", dequeue(src, dest));  // 2
    printf("出隊: %d\n", dequeue(src, dest));  // 3
    printf("出隊: %d\n", dequeue(src, dest));  // 4
    printf("出隊: %d\n", dequeue(src, dest));  // 5
    
    return 0;
}