1、隊列實現棧原理簡述

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

2、隊列實現棧方案和實現

方案1：

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

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

一個棧輸出元素順序

兩個隊列queue1和queue2模擬棧

在數據結構與算法篇-隊列和數據結構與算法篇-棧文章里我們詳細介紹了隊列和棧的原理，并都用C實現了隊列和棧。現在我們復用這兩篇文章里隊列的實現代碼，用于實現棧。定義棧相關數據結構和操作函數代碼如下：

棧初始化函數實現：

棧銷毀函數實現：

入棧函數實現：

出棧函數實現：

判斷棧是否空和是否滿函數實現：

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

單個隊列模擬出棧函數實現如下：

棧實現驗證

下面我們寫一個小程序驗棧實現的正確性。

編譯運行輸出如下：

隊列模擬棧完全正確。

責任編輯：lq6