C語言棧與佇列相互實現詳解

一、本章重點

• 用兩個佇列實現棧
• 用兩個棧實現佇列
• 解題思路總結

二、佇列實現棧

 我們有兩個佇列：

 入棧資料1、 2、 3

可以將資料入佇列至佇列一或者佇列二。

如何出棧？

但出棧要先出1，怎麼辦？

第一步：

將佇列一出隊n-1個至佇列二。

 第二步：

pop佇列一的最後一個元素。

 接下來怎麼入棧呢？

將元素入隊至不為空的佇列。

怎麼判斷棧空？

佇列一和佇列二都為空的情況下，棧就是空的。

如何取棧頂元素？

取不為空的佇列尾部元素。

總的來說就是，入棧時就將資料插入不為空的佇列，出棧就將不為空的佇列的前n-1個資料匯入至另一個佇列，然後pop最後一個元素。

程式碼實現：

 首先我們要構造一個棧。

這個棧要包含兩個佇列

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

在此之前我們要準備好佇列的一般介面：

我這裡的佇列是用單連結串列來構建的，具體介面實現可以看我之前的文章。

typedef int QTypeData;
typedef struct QueueNode
{
	struct QueueNode* next;
	QTypeData val;
}QN;
 
void QueueInit(Queue* pq)//初始化佇列
size_t QueueSize(Queue* pq)//求佇列元素個數
int QueueBack(Queue* pq)//取佇列尾部資料
void QueuePush(Queue* pq, QTypeData x)//將x入隊
void QueuePop(Queue* pq)//出隊
void QueueDestroy(Queue* pq)//結束佇列

我們要用佇列實現棧的介面：

• 第一個介面：建立並初始化棧

介面一：MyStack* myStackCreate()

這樣做行嗎？

MyStack* myStackCreate()
{
 
    MyStack ms;
    QueueInit(&ms.q1);
    QueueInit(&ms.q2);
    return ms;
}

很顯然，返回區域性變數的地址是不明智的，因為在函數返回時，ms開闢的空間會重新交給作業系統，再次存取就是非法操作。

因此我們需要將ms開闢在堆區。

參考程式碼：

• 第二個介面：入棧

介面二：void myStackPush(MyStack* obj, int x)

入棧簡單：只要將資料插入到不為空的佇列即可。

入棧之前我們需要判斷佇列滿嗎？

不需要，因為我的佇列是用單連結串列實現的，可以無限連結下去。

如果兩個佇列都為空，該插入到哪個佇列呢？

我們可以這樣做，如果佇列1為空，就插入到佇列2，如果不為空，就插入到佇列1.

參考程式碼：

• 第三個介面：出棧

介面三：int myStackPop(MyStack* obj) //出棧

再次回顧一下我們是如何出棧的。

首先我們有兩個佇列

初始狀態它們都是空的

佇列一：空

佇列二：空

入棧1、2、3、4

執行後

佇列一：空

佇列二：1、2、3、4

出佇列只能先出1，如何出4呢？

把1、2、3先出給佇列一

執行後

佇列一：1、2、3

佇列二：4

然後將4用變數記錄並出隊，最後返回記錄4的變數。

執行後

佇列一：1、2、3

佇列二：空。

出隊三板斧

第一步：即將不為空的佇列的前n-1個元素入至為空的佇列。

第二步：將剩下的1個元素用變數記錄，然後將最後一個元素出隊。

第三步：返回用變數記錄的元素。

需要注意的是：如果棧為空，那麼就返回false。

參考程式碼：

• 第四個介面：取棧頂元素

介面四：int myStackTop(MyStack* obj) //取棧頂元素

取棧頂元素之前我們需要保證棧不為空

如果棧為空，返回false。

取棧頂元素，即取不為空的佇列的隊尾元素。

參考程式碼：

• 第五個介面：判斷棧是否為空

介面五：bool myStackEmpty(MyStack* obj) //判斷棧是否為空

如果兩個佇列都是空的那麼該棧就是空的。

這裡多提一下，棧的元素個數怎麼求？

棧的元素個數就是那個不為空佇列的元素個數。

參考程式碼：

• 第六個介面：銷燬棧

介面六：void myStackFree(MyStack* obj) //結束棧

參考程式碼：

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

最後需要注意的是：呼叫棧為空的介面時，要先宣告！！

三、棧實現佇列

 第一次入隊

將資料1出隊操作

將棧1的資料全匯入棧2

然後棧2進行出棧操作

 再次入隊5、6、7

直接將5、6、7入棧至棧1

 實際我們的對頭和隊尾是這樣的

 總的來說：

用兩個棧實現一個佇列，就得把一個棧專門入隊，另一個棧用作出隊。這裡實現的時候我們用棧1做入隊棧，棧2做出隊棧。

也就是說，只要將資料入隊，直接放入棧1.

出隊就直接出棧2的資料，如果棧2為空，這將棧1的資料全部匯入棧2.

佇列的結構體：

typedef struct 
{
    ST st1;
    ST st2;
} MyQueue;

我們需要準備的棧

typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;

這裡我用的是動態陣列實現的棧

需要提前準備棧的介面：

void STInit(ST* p)
void STDestroy(ST* p)
void STPush(ST* p,STDataType x)
void STPop(ST* p)
bool STEmpty(ST* p)
int STSize(ST* p)
STDataType STRear(ST* p)

• 第一個介面：建立並初始化佇列

MyQueue* myQueueCreate() 

同樣的，需要把佇列開闢在堆區，同時對棧1和棧2進行初始化。

參考程式碼：

MyQueue* myQueueCreate() 
{
    MyQueue* mq=(MyQueue*)malloc(sizeof(MyQueue));
    assert(mq);
    STInit(&mq->st1);
    STInit(&mq->st2);
    return mq;
}

• 第二個介面：入隊

void myQueuePush(MyQueue* obj, int x) 

我們把棧1做入隊棧，棧2做出隊棧。

也就是說，只要將資料入隊，直接放入棧1.

出隊就直接出棧2的資料，如果棧2為空，這將棧1的資料全部匯入棧2.

參考程式碼：

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

• 第三個介面：出隊

int myQueuePop(MyQueue* obj) 

先要判斷佇列是否為空，如果佇列為空則返回false。

其次如果棧2為空，就將棧1的資料全匯入棧2.

參考程式碼：

int myQueuePop(MyQueue* obj) 
{
    if(myQueueEmpty(obj))
    {
        return false;
    }
    if(STEmpty(&obj->st2))
    {
        int n=STSize(&obj->st1);
        while(n--)
        {
            STPush(&obj->st2,STRear(&obj->st1));
            STPop(&obj->st1);
        }
    }
    int ret=STRear(&obj->st2);
    STPop(&obj->st2);
    return ret;
}

第四個介面：取隊頭元素

int myQueuePeek(MyQueue* obj)

取隊頭元素之前，要判斷佇列是否為空，如果為空，則返回false

隊頭元素即棧2的尾部元素。

但如果棧2為空呢？

那佇列的隊頭元素就是棧1的頭部元素。

參考程式碼：

int myQueuePeek(MyQueue* obj) 
{
    if(myQueueEmpty(obj))
    {
        return false;
    }
    if(STEmpty(&obj->st2))
    {
        return STFront(&obj->st1);
    }
    return STRear(&obj->st2);
}

第五個介面：判斷佇列是否為空

bool myQueueEmpty(MyQueue* obj)

佇列為空，需要棧1和棧2都為空。

參考程式碼：

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->st1) && STEmpty(&obj->st2);
}

第六個介面：銷燬佇列

void myQueueFree(MyQueue* obj) 

參考程式碼：

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->st1);
    STDestroy(&obj->st2);
    free(obj);
}

注意：當使用判斷佇列是否為空的介面時，注意是否在之前宣告過了。

四、解題思路總結

1.用佇列實現棧：

我們需要用兩個佇列實現棧

棧類是於尾插尾刪

佇列是尾插頭刪

第一次入棧：兩個佇列都為空，隨便插入一個佇列都可

第一次出棧：出棧要出的是尾部資料，佇列只能出頭部資料，這是佇列不能直接實現的。

那麼需要將不為空的佇列前n-1個資料匯入至為空的佇列，再將最後一個元素pop掉。

佇列一：1、2、3、4

佇列二：空

那麼匯入後

佇列一：4

佇列二：1、2、3

最後pop最後一個元素

佇列一：空

佇列二：1、2、3、4

再次尾插：尾插至不為空的佇列即可。

2.用棧實現佇列

我們有兩個棧要求實現佇列的一般介面

棧一：空

棧二：空

第一次入隊：入棧至棧一或者棧二都可，這裡選擇棧一。

假設入隊1、2、3、4

棧一：1、2、3、4

棧二:空

出隊：要先出1

將棧一全部匯入棧二

棧一：空

棧二：4、3、2、1

之後入隊就插入至棧一

出隊就pop棧二。

到此這篇關於C語言棧與佇列相互實現詳解的文章就介紹到這了,更多相關C語言 棧與佇列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！