一、引言

在數據結構的學習中，我們經常會遇到一些有趣的問題，比如如何用一種數據結構去實現另一種數據結構的功能。本文將深入探討 “用棧實現隊列” 這一經典問題，詳細解析解題思路、代碼實現以及每個函數的作用，幫助讀者更好地理解數據結構之間的轉換與應用。

練習題：

1.力扣 232. 用棧實現隊列

二、解題思路

隊列的特點是先進先出（FIFO），而棧的特點是后進先出（LIFO）。為了用棧實現隊列，我們使用兩個棧：pushST?和?popST。

• 入隊操作（push）：直接將元素壓入?pushST?棧。
• 出隊操作（pop）和獲取隊頭元素（peek）：若?popST?棧為空，將?pushST?棧中的所有元素依次彈出并壓入?popST?棧，此時?popST?棧的棧頂元素就是隊列的隊頭元素，然后進行相應的彈出（pop）或返回（peek）操作。
• 判空操作（empty）：只有當?pushST?和?popST?兩個棧都為空時，隊列才為空。

三、數據結構定義

typedef int STDataType;
typedef struct Stack {STDataType* _a;int _top;int _capacity;
} Stack;typedef struct {Stack pushST;Stack popST;
} MyQueue;

• Stack?結構體表示棧，包含存儲數據的數組?_a、棧頂指針?_top?和容量?_capacity。
• MyQueue?結構體包含兩個棧?pushST?和?popST，用于實現隊列功能。

四、棧的基礎操作函數詳解

1. 棧初始化（StackInit）

void StackInit(Stack* ps) {ps->_a = NULL;ps->_capacity = ps->_top = 0;
}

• 功能：初始化棧，將棧的存儲數組、容量和棧頂指針都置為初始狀態。
• 步驟：將?_a?置為?NULL，_capacity?和?_top?置為?0，表示空棧。

2. 入棧操作（StackPush）

void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps->_capacity == ps->_top) {int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("Fail realloc");exit(1);}ps->_a = tmp;ps->_capacity = newCapacity;}ps->_a[ps->_top++] = data;
}

• 功能：將元素壓入棧頂。
• 步驟：
  1. 檢查棧是否已滿，若滿則擴容（初始容量為 4，每次擴容為原來的 2 倍）。
  2. 擴容后將新元素插入到棧頂位置，更新?_top?指針。

三、隊列操作函數詳解

1.?myQueueCreate：創建隊列

MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;
}

?

• 功能：創建隊列實例。
• 步驟：
  • 為?MyQueue?分配內存，確保存儲隊列相關數據的空間。
  • 初始化內部的?pushST(入) 和?popST(出) 棧，通過?StackInit?清空棧狀態，為后續操作做準備。

2.?myQueuePush：入隊操作

void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST, x);
}

?

• 功能：將元素加入隊列尾部。
• 原理：直接利用?pushST?棧的入棧操作。入隊操作只需關注元素添加，無需處理順序，因此直接將元素壓入?pushST，后續出隊時再通過?popST?調整順序。

3.?myQueuePop：出隊操作(取后刪)

int myQueuePop(MyQueue* obj) {if (StackEmpty(&obj->popST)) {while (!StackEmpty(&obj->pushST)) {StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;
}

?

• 功能：移除并返回隊列頭部元素。
• 步驟：
  • 檢查?popST?是否為空。若為空，需將?pushST?中元素轉移到?popST，以模擬隊列的先進先出。轉移過程：不斷獲取?pushST?棧頂元素（StackTop），壓入?popST（StackPush），再彈出?pushST?棧頂元素（StackPop）。
  • 轉移完成后，popST?棧頂即為隊列頭部元素，獲取該元素值（StackTop），彈出?popST?棧頂元素（StackPop），并返回元素值。

4.?myQueuePeek：獲取隊頭元素(取不刪)

int myQueuePeek(MyQueue* obj) {if (StackEmpty(&obj->popST)) {while (!StackEmpty(&obj->pushST)) {StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);
}

?

• 功能：返回隊列頭部元素，不彈出。
• 邏輯：與?myQueuePop?類似。先確保?popST?有元素（若?popST?空，轉移?pushST?元素），再通過?StackTop?獲取?popST?棧頂元素，即隊列頭部元素，不執行彈出操作。

5.?myQueueEmpty：判斷隊列是否為空

bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

?

• 功能：判斷隊列是否為空。
• 原理：隊列由?pushST?和?popST?共同維護，只有兩者都為空時，隊列才為空。通過同時檢查兩個棧的?StackEmpty?狀態實現判斷。

6.?myQueueFree：釋放隊列資源

void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);
}

• 功能：釋放隊列及內部棧占用的內存。
• 步驟：
  • 先調用?StackDestroy?銷毀?pushST?和?popST?棧，釋放棧內部存儲元素的內存。
  • 最后釋放隊列結構體?obj?本身的內存，完成資源清理。

六、總結

通過兩個棧的巧妙配合，我們成功地實現了隊列的功能。這種實現方式不僅加深了我們對棧和隊列特性的理解，還展示了如何通過組合數據結構來解決實際問題。在實際編程中，靈活運用數據結構的特性可以讓我們更高效地解決各種問題。希望本文的解析能幫助讀者更好地掌握這一經典實現方法。