數(shù)據(jù)結(jié)構(gòu)與算法篇-隊(duì)列實(shí)現(xiàn)棧
01—隊(duì)列實(shí)現(xiàn)棧原理簡述
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),而隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),兩者原理不難理解,使用也簡單。但是我們不僅僅要掌握數(shù)據(jù)結(jié)構(gòu)的基本原理,還要學(xué)會靈活運(yùn)用,能否靈活運(yùn)用是考察一個(gè)人對數(shù)據(jù)結(jié)構(gòu)的理解程度,也是在面試的時(shí)候經(jīng)常會考到的知識點(diǎn)?,F(xiàn)在假設(shè)面試官要求你用隊(duì)列實(shí)現(xiàn)棧,你的解決方案是什么?通過棧的基本原理我們知道,只要每次進(jìn)行stack_pop操作時(shí)將隊(duì)列里最后一個(gè)元素輸出就能模擬棧的輸出操作。02—隊(duì)列實(shí)現(xiàn)棧方案和實(shí)現(xiàn)
方案1:我們很容易想到一種解決方案,隊(duì)列queue1保存原始輸入數(shù)據(jù),隊(duì)列queue2作為臨時(shí)隊(duì)列緩存數(shù)據(jù),只要進(jìn)行stack_pop操作時(shí),先將queue1里除最后一個(gè)元素外全部出隊(duì),且出隊(duì)的數(shù)據(jù)保存在一個(gè)臨時(shí)隊(duì)列queue2里,保存queue1最后的元素,最后再將queue2里的全部元素出隊(duì),且出隊(duì)的元素重新放進(jìn)queue1里,返回保存的queue1最后的元素。
我們作了下圖便于理解2個(gè)隊(duì)列模擬棧的過程。
一個(gè)棧輸出元素順序
兩個(gè)隊(duì)列queue1和queue2模擬棧在數(shù)據(jù)結(jié)構(gòu)與算法篇-隊(duì)列和數(shù)據(jù)結(jié)構(gòu)與算法篇-棧文章里我們詳細(xì)介紹了隊(duì)列和棧的原理,并都用C實(shí)現(xiàn)了隊(duì)列和棧?,F(xiàn)在我們復(fù)用這兩篇文章里隊(duì)列的實(shí)現(xiàn)代碼,用于實(shí)現(xiàn)棧。定義棧相關(guān)數(shù)據(jù)結(jié)構(gòu)和操作函數(shù)代碼如下:
typedef?struct?stack{
????queue_arr_t?queue1;
????queue_arr_t?queue2;
}_stack_t;
extern?void?stack_init(_stack_t?*s, int?cap);
extern?void?stack_destroy(_stack_t?*s);
extern?void?stack_push(_stack_t?*s, int?data);
extern?int?stack_pop(_stack_t?*);
extern?int?stack_pop2(_stack_t?*s);
extern?bool?stack_is_empty(_stack_t?*s);
extern?bool?stack_is_full(_stack_t?*s);
棧初始化函數(shù)實(shí)現(xiàn):void stack_init(_stack_t *s, int?cap){
????if(s == NULL || cap?<= 0){
????????return;
????}
????queue_arr_init(