劍指offer 第二版（Python3）--面試題9：用兩個棧實作隊列，用兩個隊列實作棧

第2章 面試需要的基礎知識

  面試題4：二維數組中的查找

  面試題5：替換空格

  面試題6：從尾到頭列印連結清單

  面試題7：重建二叉樹

  面試題9：用兩個棧實作隊列

第3章 高品質的代碼

第4章 解決面試題的思路

第5章 優化時間和空間效率

第6章 面試中的各項能力

第7章 兩個面試案例

題目描述

牛客網 用兩個棧實作隊列

  用兩個棧來實作一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。

解題思路

牛客網

  隊列的特性是：“先入先出”，棧的特性是：“先入後出”。我們向模拟的隊列插入數 a,b,c 時，假設插入的是 stack1，此時的棧情況為：

  棧 stack1：{a,b,c}

  棧 stack2：{}

  當需要彈出一個數，根據隊列的"先進先出"原則，a 先進入，則 a 應該先彈出。但是此時 a 在 stack1 的最下面，将 stack1 中全部元素逐個彈出壓入 stack2，然後從 stack2 中彈出 a，此時的棧情況為：

  棧 stack1：{}

  棧 stack2：{c,b}

  繼續彈出一個數，b 比 c 先進入"隊列"，b 彈出，注意此時 b 在 stack2 的棧頂，可直接彈出，此時的棧情況為：

  棧 stack1：{}

  棧 stack2：{c}

  此時向模拟隊列插入一個數 d，還是插入 stack1，此時的棧情況為：

  棧 stack1：{d}

  棧 stack2：{c}

  彈出一個數，c 比 d 先進入，c 彈出，注意此時 c 在 stack2 的棧頂，可直接彈出，此時的棧情況為：

  棧 stack1：{d}

  棧 stack2：{}

  總結：

  插入時，直接插入到 stack1；

  彈出時，若 stack2 不為空，彈出 stack2 棧頂元素，如若stack2 為空，将 stack1 中的全部數逐個出棧，并入棧 stack2，再彈出 stack2 棧頂元素。

實戰

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        if self.stack2:
            return self.stack2.pop()
        return None
           

相關題目

  用兩個隊列實作一個棧

解題思路

  這個題比上一題稍微複雜一點。

  我們向模拟的隊列插入數 a ，假設插入的是 queue1，此時的棧情況為：

  棧 queue1：{a}

  棧 queue2：{}

  繼續插入數b，加入到queue2，并将queue1中數彈出到queue2中，此時隊列情況為：

  棧 queue1：{}

  棧 queue2：{b, a}

  繼續插入數c，加入到queue1，并将queue2中數彈出到queue1中，此時隊列情況為：

  棧 queue1：{c, b, a}

  棧 queue2：{}

  然後執行一次彈出操作，從非空隊列中彈出一個數，這裡從queue1中彈出c，此時隊列情況為：

  棧 queue1：{b, a}

  棧 queue2：{}

  然後插入數d，加入到queue2，并将queue1中數全部彈出到queue2中，此時隊列情況為：

  棧 queue1：{}

  棧 queue2：{d, b, a}

  然後執行一次彈出操作，從非空隊列中彈出一個數，這裡從queue2中彈出d，此時隊列情況為：

  棧 queue1：{}

  棧 queue2：{b, a}

  總結，插入操作是插入到非空隊列中，并将另一個非空隊列中的數全部彈出到該隊列中，這樣保持一個隊列為空；彈出操作是從非空隊列彈出一個數。

實戰

class Solution:
	def __init__(self,):
		self.queue1 = []
		self.queue2 = []

	def push(self, num):
		if not self.queue1:
			self.queue1.append(num)
			while self.queue2:
				self.queue1.append(self.queue2.pop(0))
		else:
			self.queue2.append(num)
			while self.queue1:
				self.queue2.append(self.queue1.pop(0))

	def pop(self,):
		if self.queue1:
			return self.queue1.pop(0)
		if self.queue2:
			return self.queue2.pop(0)
		return None