2.6 如何用兩個棧模擬隊列操作

【出自JD面試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

分析與解答：

要求用兩個棧來模擬隊列，假設使用棧A與棧B模擬隊列Q，A為插入棧，B為彈出棧，以實現隊列Q。

再假設棧A和棧B都為空，可以認為棧A提供入隊列的功能，棧B提供出隊列的功能。

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

1）如果棧B不為空，則直接彈出棧B的數據。

2）如果棧B為空，則依次彈出棧A的數據，放入棧B中，再彈出棧B的數據。

實現代碼如下：

程序的運行結果為

算法性能分析：

這種方法入隊操作的時間復雜度為O（1），出隊列操作的時間復雜度則依賴與入隊與出隊執(zhí)行的頻率。總體來講，出隊列操作的時間復雜度為O（1），當然會有個別操作需要耗費更多的時間（因為需要從兩個棧之間移動數據）。