成都網(wǎng)站設(shè)計費用濟寧seo優(yōu)化公司
目錄
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);
}