01

—

隊列實現(xiàn)棧原理簡述

棧是一種后進先出的數(shù)據(jù)結構，而隊列是一種先進先出的數(shù)據(jù)結構，兩者原理不難理解，使用也簡單。但是我們不僅僅要掌握數(shù)據(jù)結構的基本原理，還要學會靈活運用，能否靈活運用是考察一個人對數(shù)據(jù)結構的理解程度，也是在面試的時候經(jīng)常會考到的知識點。現(xiàn)在假設面試官要求你用隊列實現(xiàn)棧，你的解決方案是什么？通過棧的基本原理我們知道，只要每次進行stack_pop操作時將隊列里最后一個元素輸出就能模擬棧的輸出操作。

02—

隊列實現(xiàn)棧方案和實現(xiàn)

方案1：我們很容易想到一種解決方案，隊列queue1保存原始輸入數(shù)據(jù)，隊列queue2作為臨時隊列緩存數(shù)據(jù)，只要進行stack_pop操作時，先將queue1里除最后一個元素外全部出隊，且出隊的數(shù)據(jù)保存在一個臨時隊列queue2里，保存queue1最后的元素，最后再將queue2里的全部元素出隊，且出隊的元素重新放進queue1里，返回保存的queue1最后的元素。

我們作了下圖便于理解2個隊列模擬棧的過程。

一個棧輸出元素順序

兩個隊列queue1和queue2模擬棧

在數(shù)據(jù)結構與算法篇-隊列和數(shù)據(jù)結構與算法篇-棧文章里我們詳細介紹了隊列和棧的原理，并都用C實現(xiàn)了隊列和棧?，F(xiàn)在我們復用這兩篇文章里隊列的實現(xiàn)代碼，用于實現(xiàn)棧。定義棧相關數(shù)據(jù)結構和操作函數(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ù)實現(xiàn)：

void stack_init(_stack_t *s, int?cap){
????if(s == NULL || cap?<= 0){
????????return;
????}

????queue_arr_init(