目錄

1.實現(xiàn)方法

過程詳解

1.執(zhí)行push 1->push 2->push 3->push 4

2.執(zhí)行第一個pop

?3.執(zhí)行第二個pop

4.執(zhí)行push 5->push 6

?編輯

?5.執(zhí)行pop->pop->pop

代碼實現(xiàn)

隊列創(chuàng)建函數(shù)myQueueCreate

入隊函數(shù)myQueuePush

出隊函數(shù)myQueuePop

返回隊列開頭元素的函數(shù)myQueuePeek

判斷隊列是否為空的函數(shù)myQueueEmpty

隊列銷毀函數(shù)myQueueFree

2.提交結(jié)果

---

解決L19.【LeetCode筆記】用棧實現(xiàn)隊列(方法1)遺留未講的方法2

1.實現(xiàn)方法

過程詳解

實現(xiàn)方法和方法1有較大的不同,一個棧用于入(push)數(shù)據(jù),另一個棧(pop)用于出數(shù)據(jù)

對于"push 1->push 2->push 3->push 4->pop->pop->push 5->push 6->->pop->pop->pop"過程畫圖分析

初始化時兩個棧都為空,隨便選一個壓入數(shù)據(jù)

1.執(zhí)行push 1->push 2->push 3->push 4

2.執(zhí)行第一個pop

按隊列的性質(zhì),需要pop 1,則需要將2,3,4拿出放到另一個棧中

?3.執(zhí)行第二個pop

按隊列的性質(zhì),需要pop 2,此時直接對右側(cè)棧pop

4.執(zhí)行push 5->push 6

此時不能將5和6壓入第二個棧,會改變隊列的順序,因此需要壓入左側(cè)的棧

?5.執(zhí)行pop->pop->pop

前兩個pop將3和4出隊

最后一次pop需要將5和6壓入右側(cè)的棧才能以正確的順序出隊

通過分析,可以得出方法2的核心在:一個棧用于入數(shù)據(jù),另一個棧用于出數(shù)據(jù)

代碼實現(xiàn)

由過程詳解可知,可以專門定義一個棧用于入數(shù)據(jù),另一個棧用于出數(shù)據(jù)

typedef struct 
{ST pushst;ST popst;
} MyQueue;

隊列創(chuàng)建函數(shù)myQueueCreate

MyQueue* myQueueCreate()
{MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if (obj==NULL){perror("malloc");return NULL;}STInit(&obj->pushst);STInit(&obj->popst);return obj;
}

入隊函數(shù)myQueuePush

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

出隊函數(shù)myQueuePop

這里要分類討論,由"過程詳解"可知,要判斷棧popst是否為空,如果為空,需要將pushst的數(shù)據(jù)(前提是有數(shù)據(jù),因此還要再做一次判斷,即嵌套判斷)全部拿過來,記錄棧頂元素后再pop

int myQueuePop(MyQueue* obj) 
{if (STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}int front=STTop(&obj->popst);STPop(&obj->popst);return front;
}

返回隊列開頭元素的函數(shù)myQueuePeek

和myQueuePop類似,返回popst的棧頂元素,如果popst為空,則將需要將pushst的數(shù)據(jù)拿過來

int myQueuePeek(MyQueue* obj) 
{if (STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return =STTop(&obj->popst);
}

這里myQueuePop的第二種寫法,讓代碼更簡潔

int myQueuePop(MyQueue* obj)
{int front=myQueuePeek(obj);STPop(&obj->popst);return front;
}

注意:使用myQueuePeek前要聲明否則報錯!!!

判斷隊列是否為空的函數(shù)myQueueEmpty

當兩個棧都為空時,隊列才為空

bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

隊列銷毀函數(shù)myQueueFree

malloc是怎么開辟的,那隊列就是怎么銷毀的

結(jié)構(gòu)圖

void myQueueFree(MyQueue* obj) 
{STDestory(&obj->pushst);STDestory(&obj->popst);free(obj);
}

2.提交結(jié)果