以雙堆疊實現佇列：C語言完整實現與效能分析

核心思想

使用兩個堆疊 inStack（入隊）與 outStack（出隊）模擬佇列 FIFO 行為：

1. 入隊：直接 push 到 inStack
2. 出隊：若 outStack 為空，將 inStack 所有元素 pop 並 push 到 outStack（順序反轉），再 pop outStack 栈頂；若不空直接 pop outStack

元素 1,2,3,4,5 依序入 inStack（1 底 5 頂）→ 移至 outStack（5 底 1 頂）→ 出隊順序 1,2,3,4,5 符合 FIFO。

介面定義 SPQueue.h

#ifndef _SPQUEUE_H_
#define _SPQUEUE_H_

typedef void SPQueue;
SPQueue* SPQueue_Create();
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（依賴 LinkStack）

#include "SPQueue.h"
#include "LinkStack.h"
#include <malloc.h> #include <stdlib.h>

typedef struct {
    LinkStack *instack;
    LinkStack *outstack;
} TSPQueue;

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

void SPQueue_Destroy(SPQueue* q) { SPQueue_Clear(q); free(q); }
void SPQueue_Clear(SPQueue* q) {
    TSPQueue *qq = (TSPQueue*)q;
    if (qq) { LinkStack_Clear(qq->instack); LinkStack_Clear(qq->outstack); }
}

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

void* SPQueue_Retrieve(SPQueue* q) {
    TSPQueue *qq = (TSPQueue*)q;
    if (!qq) return NULL;
    if (LinkStack_Size(qq->outstack) == 0) {
        while (LinkStack_Size(qq->instack) > 0)
            LinkStack_Push(qq->outstack, LinkStack_Pop(qq->instack));
    }
    return LinkStack_Pop(qq->outstack);
}

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

int SPQueue_Length(SPQueue* q) {
    TSPQueue *qq = (TSPQueue*)q;
    return qq ? LinkStack_Size(qq->instack) + LinkStack_Size(qq->outstack) : 0;
}

測試主程式與執行結果

int main() {
    SPQueue* q = SPQueue_Create();
    int a[10];
    for (int i=0; i<10; i++) { a[i]=i+1; SPQueue_Append(q, &a[i]); }
    printf("Header: %d, Length: %d\n", *(int*)SPQueue_Header(q), SPQueue_Length(q));
    for (int i=0; i<5; i++) printf("%d 出隊\n", *(int*)SPQueue_Retrieve(q));
    printf("Header: %d, Length: %d\n", *(int*)SPQueue_Header(q), SPQueue_Length(q));
    for (int i=0; i<10; i++) { a[i]=i+1; SPQueue_Append(q, &a[i]); }
    while (SPQueue_Length(q) > 0) printf("%d 出隊\n", *(int*)SPQueue_Retrieve(q));
    SPQueue_Destroy(q);
    return 0;
}

Header: 1, Length: 10
1 出隊 ... 5 出隊
Header: 6, Length: 5
6 出隊 ... 10 出隊 1 出隊 ... 5 出隊 6 出隊 ... 10 出隊

複雜度分析

均攤 O(1) 因每個元素最多被搬移一次。適合頻繁入隊、批次出隊場景。