2.6 如何用兩個(gè)棧模擬隊(duì)列操作

難度系數(shù)：★★★☆☆

被考查系數(shù)：★★★★☆

分析與解答：

題目要求用兩個(gè)棧來(lái)模擬隊(duì)列，假設(shè)使用棧A與棧B模擬隊(duì)列Q，A為插入棧，B為彈出棧，以實(shí)現(xiàn)隊(duì)列Q。

再假設(shè)A和B都為空，可以認(rèn)為棧A提供入隊(duì)列的功能，棧B提供出隊(duì)列的功能。

要入隊(duì)列，入棧A即可，而出隊(duì)列則需要分兩種情況考慮：

（1）如果棧B不為空，則直接彈出棧B的數(shù)據(jù)。

（2）如果棧B為空，則依次彈出棧A的數(shù)據(jù)，放入棧B中，再?gòu)棾鰲的數(shù)據(jù)。

實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

算法性能分析：

這種方法入隊(duì)操作的時(shí)間復(fù)雜度為O(1)，出隊(duì)列操作的時(shí)間復(fù)雜度則依賴于入隊(duì)與出隊(duì)執(zhí)行的頻率。總體來(lái)講，出隊(duì)列操作的時(shí)間復(fù)雜度為O(1)，當(dāng)然會(huì)有個(gè)別操作需要耗費(fèi)更多的時(shí)間（因?yàn)樾枰獜膬蓚€(gè)棧之間移動(dòng)數(shù)據(jù)）。