一、用棧實(shí)現(xiàn)隊(duì)列
具體題目可以參考LeetCode232. 用棧實(shí)現(xiàn)隊(duì)列
首先要想到的是，隊(duì)列是一種先進(jìn)先出的結(jié)構(gòu)，而棧是一種先進(jìn)后出的結(jié)構(gòu)。依此我們可以定義兩個棧結(jié)構(gòu)來模擬先進(jìn)先出，既然要定義兩個棧，那么為了方便調(diào)用，我們可以將這兩個棧結(jié)構(gòu)定義在一個結(jié)構(gòu)體中，如下：
typedef struct {
ST st1;//棧1
ST st2;//棧2
} MyQueue;
實(shí)現(xiàn) MyQueue類：
-
void push(int x)將元素x推到隊(duì)列的末尾； -
int pop()從隊(duì)列的開頭移除并返回元素； -
int peek()返回隊(duì)列開頭的元素； -
boolean empty()如果隊(duì)列為空，返回true；否則，返回false。
1.1初始化隊(duì)列
我們定義的結(jié)構(gòu)體在主函數(shù)外部，為了讓每個函數(shù)都能用到，那么我們就必須要用malloc來動態(tài)開辟空間，這樣此結(jié)構(gòu)會被保存在靜態(tài)區(qū)，每次函數(shù)調(diào)用時便不會銷毀此變量，然后再將此結(jié)構(gòu)體中的棧初始化。
MyQueue* myQueueCreate()
{
MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));//動態(tài)開辟結(jié)構(gòu)體變量
//注意初始化棧的參數(shù)為地址
StackInit(&queue->st1);//初始化棧1
StackInit(&queue->st2);//初始化棧2
return queue;
}
1.2模擬入隊(duì)列
我們可以將棧1作為存數(shù)據(jù)的棧，那么每次入隊(duì)列操作就是進(jìn)棧操作（StackPush(&obj->st1, x);）。
void myQueuePush(MyQueue* obj, int x)
{
assert(obj);
StackPush(&obj->st1, x);
}
1.3模擬出隊(duì)列
-
思路1：
如果我們用棧1obj->st1來存放數(shù)據(jù)，在模擬出隊(duì)列時我們首先要斷言棧1不為空，那么當(dāng)棧1不為空且我們需要出隊(duì)列頭元素時。此時就需要棧2obj->st2來暫存數(shù)據(jù)，即我們將棧1除棧底的全部元素都出棧并入棧到棧2obj->st2，然后再出棧1最后的元素并返回，這樣就模擬了先入先出性質(zhì)。還需要注意的是在返回最后一個元素前還需要再將所有數(shù)據(jù)從棧2再入到棧1。邏輯如下：
-
思路2：
棧1用來存數(shù)據(jù)，棧2用來出數(shù)據(jù)。 那么為什么棧2的元素可以直接出呢？當(dāng)我們需要模擬出隊(duì)列時，我們可以先將棧1中所以元素出棧并入棧到棧2，這樣一來?xiàng)?中的top就相當(dāng)于隊(duì)列頭元素。每次從棧2中出元素時要先判斷棧2中是否有元素，若沒有，就將棧1中的元素出棧并入棧到棧2中。大致邏輯如下：
與思路一相比較，思路二棧2無需重新入棧1，還可繼續(xù)模擬出隊(duì)列。只能說兩種思路各有好處，下列代碼實(shí)現(xiàn)使用的是思路一：
int myQueuePop(MyQueue* obj)
{
assert(obj);
assert(StackSize(&obj->st1) != 0);//棧1不為空
ST* empty = &obj->st2;//棧2為空
ST* noempty = &obj->st1;//棧1不為空
//將棧1除棧底的所有元素出棧并入棧到棧2
while(StackSize(noempty) > 1)
{
StackPush(empty,StackTop(noempty));
StackPop(noempty);
}
//找到隊(duì)頭
int ret = StackTop(noempty);
StackPop(noempty);
//重新入棧1
while(StackSize(empty) > 0)
{
StackPush(noempty,StackTop(empty));
StackPop(empty);
}
return ret;
}
1.4取模擬的隊(duì)列頭元素
此函數(shù)實(shí)現(xiàn)與1.3模擬出隊(duì)列方法相似，就不多介紹了，如下：
int myQueuePeek(MyQueue* obj)
{
assert(obj);
ST* empty = &obj->st2;
ST* noempty = &obj->st1;
//將棧1除棧底的所有元素出棧并入棧到棧2
while(StackSize(noempty) > 1)
{
StackPush(empty,StackTop(noempty));
StackPop(noempty);
}
//找到隊(duì)頭
int ret = StackTop(noempty);
StackPush(empty,ret);
StackPop(noempty);
//重新入棧1
while(StackSize(empty) > 0)
{
StackPush(noempty,StackTop(empty));
StackPop(empty);
}
return ret;
}
1.5判斷隊(duì)列是否為空
依據(jù)上面思路，因?yàn)闂?是用來存數(shù)據(jù)的，所以當(dāng)棧1為空時就代表我們模擬的隊(duì)列為空。
bool myQueueEmpty(MyQueue* obj)
{
assert(obj);
return StackEmpty(&obj->st1);
}
二、用隊(duì)列實(shí)現(xiàn)棧
具體題目可以參考LeetCode225. 用隊(duì)列實(shí)現(xiàn)棧
與用棧實(shí)現(xiàn)隊(duì)列相似，我們同樣需要兩個隊(duì)列來模擬實(shí)現(xiàn)棧，且關(guān)鍵在于還原隊(duì)列先入先出的性質(zhì)，依此性質(zhì)來實(shí)現(xiàn)函數(shù)。既然這樣我們可以如下定義結(jié)構(gòu)體：
typedef struct
{
Queue* q1;//隊(duì)列1
Queue* q2;//隊(duì)列2
} MyStack;
我們可以看到與模擬隊(duì)列不同的是，模擬棧的結(jié)構(gòu)體中存放的是兩個結(jié)構(gòu)體指針，這與隊(duì)列的實(shí)現(xiàn)方法有關(guān)。因?yàn)?strong>我們用的隊(duì)列是用鏈表實(shí)現(xiàn)的，所以其每個節(jié)點(diǎn)都是組成隊(duì)列的一部分，且我們應(yīng)該通過指針將他們一個個都連接起來（即通過指針來尋找節(jié)點(diǎn)）。
至于用棧實(shí)現(xiàn)隊(duì)列問題中的結(jié)構(gòu)體我們存放的是兩個關(guān)于棧的結(jié)構(gòu)體，是因?yàn)?strong>我們所使用的棧使用數(shù)組來實(shí)現(xiàn)的，這樣一來我們操作的就是棧結(jié)構(gòu)體中某一個元素（即動態(tài)開辟的數(shù)組）。當(dāng)然在我們也可以放兩個棧結(jié)構(gòu)體指針，只不過在下面初始化隊(duì)列時（myQueueCreate() ）我們需要額外malloc動態(tài)開辟棧結(jié)構(gòu)大小的空間，然后將指針指向該空間的地址。
實(shí)現(xiàn) MyStack類：
-
void push(int x)將元素x壓入棧頂； -
int pop()移除并返回棧頂元素； -
int top()返回棧頂元素； -
boolean empty()如果棧是空的，返回true；否則，返回false。
2.1初始化棧
malloc()動態(tài)開辟棧結(jié)構(gòu)體沒什么問題，與模擬隊(duì)列相似。但為什么還要給結(jié)構(gòu)體中的兩個隊(duì)列結(jié)構(gòu)體指針動態(tài)開辟空間呢？這樣不就違背了我們上面探討的問題了嗎？其實(shí)不然，這里的兩個結(jié)構(gòu)體指針事實(shí)上指向的是存放隊(duì)列頭指針和尾指針的結(jié)構(gòu)體，如下：
typedef struct Queue
{
QNode* phead;//隊(duì)列頭指針
QNode* ptail;//隊(duì)列尾指針
int size;//長度
}Queue;
這樣一來，基本每個函數(shù)都需要用到此結(jié)構(gòu)體，那么我們就必須malloc開辟來增加作用域和生命周期。 最后再初始化這兩個存放頭/尾指針的結(jié)構(gòu)體，并返回用來模擬棧的結(jié)構(gòu)體地址。
MyStack* myStackCreate()
{
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
pst->q1 = (Queue*)malloc(sizeof(Queue));
pst->q2 = (Queue*)malloc(sizeof(Queue));
QueueInit(pst->q1);
QueueInit(pst->q2);
return pst;
}
2.2模擬出棧
與模擬出隊(duì)列不同的是，這里用來模擬出棧的兩個隊(duì)列都可以用來出棧和入棧，具體方法如下：
為了還原棧先入后出的性質(zhì)，我們可以先找到不為空的隊(duì)列（因?yàn)閮蓚€隊(duì)列都有可能有數(shù)據(jù)，但不同時有），然后將有數(shù)據(jù)的隊(duì)列（noempty）除隊(duì)尾的一個節(jié)點(diǎn)全都出隊(duì)列并入隊(duì)列到無數(shù)據(jù)的隊(duì)列（empty），這樣一來就找到了尾節(jié)點(diǎn)（模擬的棧頂）。還需要注意的是，此時我們無需再將數(shù)據(jù)重新入到noempty。 邏輯大致如下：
int myStackPop(MyStack* obj)
{
//先假設(shè)隊(duì)列1為空
Queue* empty = obj->q1;
Queue* noempty = obj->q2;
//糾正
if(QueueEmpty(obj->q2))
{
empty = obj->q2;
noempty = obj->q1;
}
//noempty出，并入到empty
while(QueueSize(noempty) > 1)
{
int cmp = QueueFront(noempty);
QueuePop(noempty);
QueuePush(empty, cmp);
}
//取到模擬的棧頂元素
int ret = QueueFront(noempty);
QueuePop(noempty);
return ret;
}
2.3模擬入棧
依據(jù)上面的方法，我們是要將數(shù)據(jù)入到不為空的隊(duì)列，簡單的if語句便可完成篩選。
void myStackPush(MyStack* obj, int x)
{
assert(obj);
if(!QueueEmpty(obj->q1))
{
QueuePush(obj->q1, x);
}
else
{
QueuePush(obj->q2, x);
}
}
2.4取模擬的棧頂元素
同樣我們需要找到不為空的那個隊(duì)列，且事實(shí)上隊(duì)列尾指針指向的那個節(jié)點(diǎn)就是模擬的棧的棧頂，我們只需返回此元素即可。文章來源：http://www.zghlxwxcb.cn/news/detail-768470.html
int myStackTop(MyStack* obj)
{
assert(obj);
//找不為空的隊(duì)列
if(!QueueEmpty(obj->q1))
return QueueBack(obj->q1);
else
return QueueBack(obj->q2);
}
2.5判讀棧是否為空
當(dāng)兩個隊(duì)列都沒有數(shù)據(jù)時，那么模擬的棧就是空棧。文章來源地址http://www.zghlxwxcb.cn/news/detail-768470.html
bool myStackEmpty(MyStack* obj)
{
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】---棧和隊(duì)列的互相實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
