隊(duì)列實(shí)現(xiàn)棧原理是什么？隊(duì)列實(shí)現(xiàn)棧方案有哪幾種？

1、隊(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)用是考察一個人對數(shù)據(jù)結(jié)構(gòu)的理解程度，也是在面試的時(shí)候經(jīng)常會考到的知識點(diǎn)?，F(xiàn)在假設(shè)面試官要求你用隊(duì)列實(shí)現(xiàn)棧，你的解決方案是什么？通過棧的基本原理我們知道，只要每次進(jìn)行stack_pop操作時(shí)將隊(duì)列里最后一個元素輸出就能模擬棧的輸出操作。

2、隊(duì)列實(shí)現(xiàn)棧方案和實(shí)現(xiàn)

方案1：

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

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

一個棧輸出元素順序

兩個隊(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ù)代碼如下：

棧初始化函數(shù)實(shí)現(xiàn)：

棧銷毀函數(shù)實(shí)現(xiàn)：

入棧函數(shù)實(shí)現(xiàn)：

出棧函數(shù)實(shí)現(xiàn)：

判斷棧是否空和是否滿函數(shù)實(shí)現(xiàn)：

從方案1我們知道每次出隊(duì)都需要將隊(duì)列里除最后一個元素外的元素保存在另外一個臨時(shí)隊(duì)列里，增加了空間復(fù)雜度。那么能否只用一個隊(duì)列能否模擬棧呢？通過仔細(xì)觀察方案1發(fā)現(xiàn)queue1出對的數(shù)據(jù)是可以重新再入隊(duì)的，只要讓隊(duì)列里最后一個元素在隊(duì)列頭即可，那么我們很容易想到方案2。 方案2： 將隊(duì)列queue1里的數(shù)據(jù)依次出隊(duì)，且出隊(duì)的數(shù)據(jù)重新放在queue1的隊(duì)尾，直到最后一個元素在隊(duì)列頭，最后輸出隊(duì)列頭的元素即可。整個過程我們可以用下圖表示。單個隊(duì)列模擬棧

單個隊(duì)列模擬出棧函數(shù)實(shí)現(xiàn)如下：

棧實(shí)現(xiàn)驗(yàn)證

下面我們寫一個小程序驗(yàn)棧實(shí)現(xiàn)的正確性。

編譯運(yùn)行輸出如下：

隊(duì)列模擬棧完全正確。

責(zé)任編輯：lq6