一、本章重點

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

二、隊列實現棧

?我們有兩個隊列：

?入棧數據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棧二。