兩個棧實現隊列：C 語言完整實現與 amortized O(1) 複雜度分析

編輯：關於C語言

核心思想

利用兩個棧 inStack (入隊棧) 和 outStack (出隊棧) 模擬隊列 FIFO 語義：
- 入隊：直接 push 到 inStack。
- 出隊：若 outStack 為空，將 inStack 所有元素 pop 並 push 到 outStack (順序反轉)，再 pop outStack 棧頂。
- 攤還分析：每個元素最多經歷兩次 push、兩次 pop，單次操作均攤 O(1)。

ADT 介面設計

// SPQueue.h
#ifndef _SPQUEUE_H_
#define _SPQUEUE_H_

typedef void SPQueue; // 不透明指針

SPQueue* SPQueue_Create(void);
void SPQueue_Destroy(SPQueue* queue);
void SPQueue_Clear(SPQueue* queue);
int SPQueue_Append(SPQueue* queue, void* item);   // 入隊
void* SPQueue_Retrieve(SPQueue* queue);           // 出隊
void* SPQueue_Header(SPQueue* queue);             // 取隊首
int SPQueue_Length(SPQueue* queue);               // 長度

#endif

內部結構與實現

// SPQueue.c
#include "SPQueue.h"
#include "LinkStack.h" // 單向鏈表實現的棧
#include 

typedef struct {
    LinkStack* inStack;
    LinkStack* outStack;
} TSPQueue;

SPQueue* SPQueue_Create() {
    TSPQueue* q = malloc(sizeof(TSPQueue));
    if (!q) return NULL;
    q->inStack = LinkStack_Create();
    q->outStack = LinkStack_Create();
    if (!q->inStack || !q->outStack) {
        LinkStack_Destroy(q->inStack);
        LinkStack_Destroy(q->outStack);
        free(q);
        return NULL;
    }
    return (SPQueue*)q;
}

void SPQueue_Destroy(SPQueue* queue) {
    SPQueue_Clear(queue);
    free(queue);
}

void SPQueue_Clear(SPQueue* queue) {
    TSPQueue* q = (TSPQueue*)queue;
    if (q) {
        LinkStack_Clear(q->inStack);
        LinkStack_Clear(q->outStack);
    }
}

int SPQueue_Append(SPQueue* queue, void* item) {
    TSPQueue* q = (TSPQueue*)queue;
    return q ? LinkStack_Push(q->inStack, item) : 0;
}

void* SPQueue_Retrieve(SPQueue* queue) {
    TSPQueue* q = (TSPQueue*)queue;
    if (!q) return NULL;

    // outStack 為空時，倒數 inStack
    if (LinkStack_Size(q->outStack) == 0) {
        while (LinkStack_Size(q->inStack) > 0) {
            LinkStack_Push(q->outStack, LinkStack_Pop(q->inStack));
        }
    }
    return LinkStack_Pop(q->outStack);
}

void* SPQueue_Header(SPQueue* queue) {
    TSPQueue* q = (TSPQueue*)queue;
    if (!q) return NULL;
    if (LinkStack_Size(q->outStack) == 0) {
        while (LinkStack_Size(q->inStack) > 0) {
            LinkStack_Push(q->outStack, LinkStack_Pop(q->inStack));
        }
    }
    return LinkStack_Top(q->outStack);
}

int SPQueue_Length(SPQueue* queue) {
    TSPQueue* q = (TSPQueue*)queue;
    return q ? LinkStack_Size(q->inStack) + LinkStack_Size(q->outStack) : 0;
}

測試驗證

int main() {
    SPQueue* q = SPQueue_Create();
    int a[10] = {1,2,3,4,5,6,7,8,9,10};

    // 第一批入隊
    for (int i=0; i<10; i++) SPQueue_Append(q, &a[i]);
    printf("Header: %d, Len: %d\n", *(int*)SPQueue_Header(q), SPQueue_Length(q));

    // 出隊 5 個
    for (int i=0; i<5; i++) printf("%d 出隊\n", *(int*)SPQueue_Retrieve(q));

    // 第二批入隊
    for (int i=0; i<10; i++) SPQueue_Append(q, &a[i]);

    // 全部出隊
    while (SPQueue_Length(q) > 0) printf("%d 出隊\n", *(int*)SPQueue_Retrieve(q));

    SPQueue_Destroy(q);
    return 0;
}

輸出：
Header: 1, Len: 10
1 出隊 ... 5 出隊
Header: 6, Len: 5
6 出隊 ... 10 出隊 1 出隊 ... 10 出隊
完美符合 FIFO 順序。