在上一篇優化後隊列的實現(C語言實現) 中，雖然我們對隊列的時間復雜度進行了優化，但是卻讓代碼的可讀性變差了，代碼顯得略微臃腫（當然，這些話你看看就好，主要是為了奉承這篇博文的）。
這裡主要實現的是：利用棧來實現隊列
基本思路：
1，創建兩個棧
2，兩個棧合並起來組裝成一個隊列，分別取名為instack,outstack，用於進隊列，出隊列
3，比如有1,2,3,4,5 需要進入隊列，先將這一串數壓入instack棧中，假設壓入順序為1,2,3,4,5（1為棧底），再將instack中的數據移入outstack中，出棧順序為：5,4,3,2,1. 那麼入outsatck的時候，進棧的順序同樣為 ： 5,4,3,2,1（5為棧底），那麼出outstack的時候，順序即為：1,2,3,4,5 這樣就做到了入是1,2,3,4,5 出也是1,2,3,4,5 這樣就跟隊列是一樣一樣的了。
代碼實現思路：
實現思路
准備兩個棧用於實現隊列：inStack和outStack
當有新元素入隊時： ：將其壓入 將其壓入inStack中
當需要出隊時：
當outStack為空時：
1. 將inStack中的元素逐一彈出並壓入outStack中
2. 將outStack的棧頂元素彈出
當outStack不為空時：
– 直接將outStack的棧頂元素彈出
源代碼入下：
這裡用到了棧的代碼，具體可以參閱：棧的實現與操作(C語言實現)
頭文件：
#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
// 棧實現隊列.cpp : 定義控制台應用程序的入口點。 // #include "stdafx.h" #include "SPQueue.h" #include "LinkStack.h" #include#include typedef struct { LinkStack * instack; LinkStack * outstack; } TSPQueue; int _tmain(int argc, _TCHAR* argv[]) { SPQueue* queue = SPQueue_Create(); int a[10] = {0}; int i = 0; for(i=0; i<10; i++) { a[i] = i + 1; SPQueue_Append(queue, a + i); } printf("第一次進隊列："); printf("Header: %d\n", *(int*)SPQueue_Header(queue)); printf("Length: %d\n", SPQueue_Length(queue)); for(i=0; i<5; i++) { printf("%d\t出隊列了\n", *(int*)SPQueue_Retrieve(queue)); } printf("\n第二次進隊列：\n"); printf("Header: %d\n", *(int*)SPQueue_Header(queue)); printf("Length: %d\n", SPQueue_Length(queue)); for(i=0; i<10; i++) //繼續尾加10個節點 { a[i] = i + 1; SPQueue_Append(queue, a + i); } while( SPQueue_Length(queue) > 0 ) { printf("%d\t出隊列了\n", *(int*)SPQueue_Retrieve(queue)); } SPQueue_Destroy(queue); system("pause"); return 0; } //創建 SPQueue* SPQueue_Create() { TSPQueue* ret = (TSPQueue*)malloc(sizeof(TSPQueue)); if (NULL != ret) { ret->instack = LinkStack_Create(); ret->outstack = LinkStack_Create(); if ((NULL == ret->instack) && (NULL == ret->outstack)) { LinkStack_Destroy(ret->instack); LinkStack_Destroy(ret->outstack); free(ret); ret = NULL; } } return ret; } //銷毀 void SPQueue_Destroy(SPQueue* queue) { SPQueue_Clear(queue); free(queue); } //清空 void SPQueue_Clear(SPQueue* queue) { TSPQueue* SPQueue = (TSPQueue*)queue; if (NULL != SPQueue) { LinkStack_Clear(SPQueue->instack); LinkStack_Clear(SPQueue->outstack); } } //尾加 int SPQueue_Append(SPQueue* queue, void* item) { TSPQueue* SPQueue = (TSPQueue*)queue; int ret = 0; if (NULL != SPQueue) { ret = LinkStack_Push(SPQueue->instack,item); } return ret; } //刪除頭部 void* SPQueue_Retrieve(SPQueue* queue) { TSPQueue* SPQueue = (TSPQueue*)queue; void * ret = NULL; if (NULL != SPQueue) { //當outstack長度為0時，把instack中的數據移入outstack if (LinkStack_Size(SPQueue->outstack) == 0) { while (LinkStack_Size(SPQueue->instack) > 0) { LinkStack_Push(SPQueue->outstack,LinkStack_Pop(SPQueue->instack)); } } //取出outstack的棧頂 ret = LinkStack_Pop(SPQueue->outstack); } return ret ; } //獲得頭部 void* SPQueue_Header(SPQueue* queue) { TSPQueue* SPQueue = (TSPQueue*)queue; void * ret = NULL; if (NULL != SPQueue) { if (LinkStack_Size(SPQueue->outstack) == 0) { while (LinkStack_Size(SPQueue->instack) > 0) { LinkStack_Push(SPQueue->outstack,LinkStack_Pop(SPQueue->instack)); } } ret = LinkStack_Top(SPQueue->outstack); } return ret ; } //長度 int SPQueue_Length(SPQueue* queue) { TSPQueue* SPQueue = (TSPQueue*)queue; int ret = 0; if (NULL != SPQueue) { ret = LinkStack_Size(SPQueue->instack) + LinkStack_Size(SPQueue->outstack); } return ret; }
第一次進隊列：Header: 1 Length: 10 1 出隊列了 2 出隊列了 3 出隊列了 4 出隊列了 5 出隊列了 第二次進隊列： Header: 6 Length: 5 6 出隊列了 7 出隊列了 8 出隊列了 9 出隊列了 10 出隊列了 1 出隊列了 2 出隊列了 3 出隊列了 4 出隊列了 5 出隊列了 6 出隊列了 7 出隊列了 8 出隊列了 9 出隊列了 10 出隊列了 請按任意鍵繼續. . .
