一、本章重點(diǎn)

• 用兩個(gè)隊(duì)列實(shí)現(xiàn)棧
• 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
• 解題思路總結(jié)

二、隊(duì)列實(shí)現(xiàn)棧

 我們有兩個(gè)隊(duì)列：

 入棧數(shù)據(jù)1、 2、 3

可以將數(shù)據(jù)入隊(duì)列至隊(duì)列一或者隊(duì)列二。

如何出棧？

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

第一步：

將隊(duì)列一出隊(duì)n-1個(gè)至隊(duì)列二。

 第二步：

pop隊(duì)列一的最后一個(gè)元素。

 接下來(lái)怎么入棧呢？

將元素入隊(duì)至不為空的隊(duì)列。

怎么判斷?？?？

隊(duì)列一和隊(duì)列二都為空的情況下，棧就是空的。

如何取棧頂元素？

取不為空的隊(duì)列尾部元素。

總的來(lái)說(shuō)就是，入棧時(shí)就將數(shù)據(jù)插入不為空的隊(duì)列，出棧就將不為空的隊(duì)列的前n-1個(gè)數(shù)據(jù)導(dǎo)入至另一個(gè)隊(duì)列，然后pop最后一個(gè)元素。

代碼實(shí)現(xiàn)：

 首先我們要構(gòu)造一個(gè)棧。

這個(gè)棧要包含兩個(gè)隊(duì)列

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

在此之前我們要準(zhǔn)備好隊(duì)列的一般接口：

我這里的隊(duì)列是用單鏈表來(lái)構(gòu)建的，具體接口實(shí)現(xiàn)可以看我之前的文章。

typedef int QTypeData;
typedef struct QueueNode
{
	struct QueueNode* next;
	QTypeData val;
}QN;
 
void QueueInit(Queue* pq)//初始化隊(duì)列
size_t QueueSize(Queue* pq)//求隊(duì)列元素個(gè)數(shù)
int QueueBack(Queue* pq)//取隊(duì)列尾部數(shù)據(jù)
void QueuePush(Queue* pq, QTypeData x)//將x入隊(duì)
void QueuePop(Queue* pq)//出隊(duì)
void QueueDestroy(Queue* pq)//結(jié)束隊(duì)列

我們要用隊(duì)列實(shí)現(xiàn)棧的接口：

• 第一個(gè)接口：創(chuàng)建并初始化棧

接口一：MyStack* myStackCreate()

這樣做行嗎？

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

很顯然，返回局部變量的地址是不明智的，因?yàn)樵诤瘮?shù)返回時(shí)，ms開(kāi)辟的空間會(huì)重新交給操作系統(tǒng)，再次訪問(wèn)就是非法操作。

因此我們需要將ms開(kāi)辟在堆區(qū)。

參考代碼：

• 第二個(gè)接口：入棧

接口二：void myStackPush(MyStack* obj, int x)

入棧簡(jiǎn)單：只要將數(shù)據(jù)插入到不為空的隊(duì)列即可。

入棧之前我們需要判斷隊(duì)列滿嗎？

不需要，因?yàn)槲业年?duì)列是用單鏈表實(shí)現(xiàn)的，可以無(wú)限鏈接下去。

如果兩個(gè)隊(duì)列都為空，該插入到哪個(gè)隊(duì)列呢？

我們可以這樣做，如果隊(duì)列1為空，就插入到隊(duì)列2，如果不為空，就插入到隊(duì)列1.

參考代碼：

• 第三個(gè)接口：出棧

接口三：int myStackPop(MyStack* obj) //出棧

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

首先我們有兩個(gè)隊(duì)列

初始狀態(tài)它們都是空的

隊(duì)列一：空

隊(duì)列二：空

入棧1、2、3、4

執(zhí)行后

隊(duì)列一：空

隊(duì)列二：1、2、3、4

出隊(duì)列只能先出1，如何出4呢？

把1、2、3先出給隊(duì)列一

執(zhí)行后

隊(duì)列一：1、2、3

隊(duì)列二：4

然后將4用變量記錄并出隊(duì)，最后返回記錄4的變量。

執(zhí)行后

隊(duì)列一：1、2、3

隊(duì)列二：空。

出隊(duì)三板斧

第一步：即將不為空的隊(duì)列的前n-1個(gè)元素入至為空的隊(duì)列。

第二步：將剩下的1個(gè)元素用變量記錄，然后將最后一個(gè)元素出隊(duì)。

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

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

參考代碼：

• 第四個(gè)接口：取棧頂元素

接口四：int myStackTop(MyStack* obj) //取棧頂元素

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

如果棧為空，返回false。

取棧頂元素，即取不為空的隊(duì)列的隊(duì)尾元素。

參考代碼：

• 第五個(gè)接口：判斷棧是否為空

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

如果兩個(gè)隊(duì)列都是空的那么該棧就是空的。

這里多提一下，棧的元素個(gè)數(shù)怎么求？

棧的元素個(gè)數(shù)就是那個(gè)不為空隊(duì)列的元素個(gè)數(shù)。

參考代碼：

• 第六個(gè)接口：銷毀棧

接口六：void myStackFree(MyStack* obj) //結(jié)束棧

參考代碼：

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

最后需要注意的是：調(diào)用棧為空的接口時(shí)，要先聲明！！

三、棧實(shí)現(xiàn)隊(duì)列

 第一次入隊(duì)

將數(shù)據(jù)1出隊(duì)操作

將棧1的數(shù)據(jù)全導(dǎo)入棧2

然后棧2進(jìn)行出棧操作

 再次入隊(duì)5、6、7

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

 實(shí)際我們的對(duì)頭和隊(duì)尾是這樣的

 總的來(lái)說(shuō)：

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，就得把一個(gè)棧專門(mén)入隊(duì)，另一個(gè)棧用作出隊(duì)。這里實(shí)現(xiàn)的時(shí)候我們用棧1做入隊(duì)棧，棧2做出隊(duì)棧。

也就是說(shuō)，只要將數(shù)據(jù)入隊(duì)，直接放入棧1.

出隊(duì)就直接出棧2的數(shù)據(jù)，如果棧2為空，這將棧1的數(shù)據(jù)全部導(dǎo)入棧2.

隊(duì)列的結(jié)構(gòu)體：

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

我們需要準(zhǔn)備的棧

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

這里我用的是動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的棧

需要提前準(zhǔn)備棧的接口：

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)

• 第一個(gè)接口：創(chuàng)建并初始化隊(duì)列

MyQueue* myQueueCreate() 

同樣的，需要把隊(duì)列開(kāi)辟在堆區(qū)，同時(shí)對(duì)棧1和棧2進(jìn)行初始化。

參考代碼：

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

• 第二個(gè)接口：入隊(duì)

void myQueuePush(MyQueue* obj, int x) 

我們把棧1做入隊(duì)棧，棧2做出隊(duì)棧。

也就是說(shuō)，只要將數(shù)據(jù)入隊(duì)，直接放入棧1.

出隊(duì)就直接出棧2的數(shù)據(jù)，如果棧2為空，這將棧1的數(shù)據(jù)全部導(dǎo)入棧2.

參考代碼：

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

• 第三個(gè)接口：出隊(duì)

int myQueuePop(MyQueue* obj) 

先要判斷隊(duì)列是否為空，如果隊(duì)列為空則返回false。

其次如果棧2為空，就將棧1的數(shù)據(jù)全導(dǎo)入棧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;
}

第四個(gè)接口：取隊(duì)頭元素

int myQueuePeek(MyQueue* obj)

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

隊(duì)頭元素即棧2的尾部元素。

但如果棧2為空呢？

那隊(duì)列的隊(duì)頭元素就是棧1的頭部元素。

參考代碼：

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

第五個(gè)接口：判斷隊(duì)列是否為空

bool myQueueEmpty(MyQueue* obj)

隊(duì)列為空，需要棧1和棧2都為空。

參考代碼：

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

第六個(gè)接口：銷毀隊(duì)列

void myQueueFree(MyQueue* obj) 

參考代碼：

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

注意：當(dāng)使用判斷隊(duì)列是否為空的接口時(shí)，注意是否在之前聲明過(guò)了。

四、解題思路總結(jié)

1.用隊(duì)列實(shí)現(xiàn)棧：

我們需要用兩個(gè)隊(duì)列實(shí)現(xiàn)棧

棧類是于尾插尾刪

隊(duì)列是尾插頭刪

第一次入棧：兩個(gè)隊(duì)列都為空，隨便插入一個(gè)隊(duì)列都可

第一次出棧：出棧要出的是尾部數(shù)據(jù)，隊(duì)列只能出頭部數(shù)據(jù)，這是隊(duì)列不能直接實(shí)現(xiàn)的。

那么需要將不為空的隊(duì)列前n-1個(gè)數(shù)據(jù)導(dǎo)入至為空的隊(duì)列，再將最后一個(gè)元素pop掉。

隊(duì)列一：1、2、3、4

隊(duì)列二：空

那么導(dǎo)入后

隊(duì)列一：4

隊(duì)列二：1、2、3

最后pop最后一個(gè)元素

隊(duì)列一：空

隊(duì)列二：1、2、3、4

再次尾插：尾插至不為空的隊(duì)列即可。

2.用棧實(shí)現(xiàn)隊(duì)列

我們有兩個(gè)棧要求實(shí)現(xiàn)隊(duì)列的一般接口

棧一：空

棧二：空

第一次入隊(duì)：入棧至棧一或者棧二都可，這里選擇棧一。

假設(shè)入隊(duì)1、2、3、4

棧一：1、2、3、4

棧二:空

出隊(duì)：要先出1

將棧一全部導(dǎo)入棧二

棧一：空

棧二：4、3、2、1

之后入隊(duì)就插入至棧一

出隊(duì)就pop棧二。

到此這篇關(guān)于C語(yǔ)言棧與隊(duì)列相互實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言 棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論