應用題 用Stack實作Queue_Leetcode #232 Implement Queue using Stacks

更新於 發佈於 閱讀時間約 5 分鐘
raw-image

這題的題目在這裡

題目敘述

題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。

也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue


測試範例

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

約束條件

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to pushpoppeek, and empty.
  • All the calls to pop and peek are valid.

 

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.


演算法

關鍵點在於用LIFO的特質,去組合、實作出FIFO的功能

其實可以這樣想,既然是LIFO,代表可以用第一個stack作為輸入的buffer,用第二個stack作為輸出的buffer。

這樣一來,每個元素等於依照順序進出了stack兩次,LIFO 再 LIFO,等價於 FIFO

例如 輸入順序是 [1, 2, 3],再逐一pop出來,再推入另一個stack,
此時變成[3, 2, 1]

這時候再依序pop出來,就會得到1, 2, 3,剛好就是我們原本想要的FIFO輸出順序。


程式碼

class MyQueue:

def __init__(self):
 """  Initialize your data structure here.  """
 self.inbox = []
 self.outbox = []
 
 

def push(self, x: int) -> None:
 """  Push element x to the back of queue.  """
 self.inbox.append( x )
 

def pop(self) -> int:
 """  Removes the element from in front of queue and returns that element.  """

 self.peek()
 return self.outbox.pop()
 
 
def peek(self) -> int:
 """  Get the front element.  """
 
 if len( self.outbox ) != 0:
  return self.outbox[-1]
 
 else:
  
  while len(self.inbox) != 0:
   
   top_of_inbox = self.inbox.pop()
   self.outbox.append( top_of_inbox )
 
  return self.outbox[-1]
 

def empty(self) -> bool:
 """  Returns whether the queue is empty.  """
 
 if len(self.inbox) + len(self.outbox) == 0:
  return True
 else:
  return False



複雜度分析

時間複雜度: amortized O(1)

init(), push(), empty() 函數的時間複雜度為O(1) 。

peek() , pop() 在每次呼叫中,會把原本的順序再翻轉一次,從LIFO轉為FIFO,平均攤銷時間複雜度為O (1)

空間複雜度: O(n)

stack所耗用最大長度就是元素總數。


關鍵知識點

關鍵點在於用LIFO的特質,去組合、實作出FIFO的功能

每個元素依照順序進出了stack兩次,LIFO 再 LIFO,等價於 FIFO


Reference:

[1] Python/JS/Java/C++ sol by two stacks [w/ Comment] - Implement Queue using Stacks - LeetCode

avatar-img
91會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
題目會給定一個字串s,把裡面的星號*視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部操作完以後,剩下的字串內容為何? 例如: abc**,最後剩下a。 說明: bc分別被右邊的星號給吃掉。
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
題目會給定我們一個串列,和一個n值,要求我們刪除尾巴數來的第n個節點。 例如 1->2->3->4->5 和 給定n值=2,要求我們刪除尾巴數來的第2個節點。 尾巴數來的第2個節點是4,刪除之後,更新連結,輸出答案如下 1->2->3->5
題目會給定我們一個n值,問我們n! 也就是n階乘 尾巴的零有多少個? 例如n=5 就是代表5! = 5x4x3x2x1=120 尾巴有一個零,回傳1
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
題目會給定一個字串s,把裡面的星號*視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部操作完以後,剩下的字串內容為何? 例如: abc**,最後剩下a。 說明: bc分別被右邊的星號給吃掉。
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
題目會給定我們一個串列,和一個n值,要求我們刪除尾巴數來的第n個節點。 例如 1->2->3->4->5 和 給定n值=2,要求我們刪除尾巴數來的第2個節點。 尾巴數來的第2個節點是4,刪除之後,更新連結,輸出答案如下 1->2->3->5
題目會給定我們一個n值,問我們n! 也就是n階乘 尾巴的零有多少個? 例如n=5 就是代表5! = 5x4x3x2x1=120 尾巴有一個零,回傳1
你可能也想看
Google News 追蹤
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
這一節要來看看,有許多個力同時作用時,該怎麼處理。
※ 好用的陣列迭代器:forEach forEach 的使用時機: 需要從頭到尾把陣列中的每一個元素都印出來 ,就適合使用 forEach 方法。 forEach 的必要參數是一個函式: forEach() 的功能是把陣列的每個元素都丟進某個函式執行一次,因此必要的參數是一個函式。 語法:
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
在Python中,queue是一個非常有用的模块。 它提供了多種佇列(queue)實現,用於在多線程環境中安全地交換信息或者數據。 佇列(queue)是一種先進先出(FIFO)的數據結構,允許在佇列的一端插入元素,另一端取出元素。(FIFO 是First In, First Out 的縮寫)
Thumbnail
本文介紹了串列運算式的應用,以及與Lambda匿名函式方法的比較,並提供了程式範例。串列運算式提供了一種簡潔的語法,用於創建、轉換和過濾列表。lambda函式用於創建匿名函式,通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。
Thumbnail
題目 : 28. Find the Index of the First Occurrence in a String
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
這一節要來看看,有許多個力同時作用時,該怎麼處理。
※ 好用的陣列迭代器:forEach forEach 的使用時機: 需要從頭到尾把陣列中的每一個元素都印出來 ,就適合使用 forEach 方法。 forEach 的必要參數是一個函式: forEach() 的功能是把陣列的每個元素都丟進某個函式執行一次,因此必要的參數是一個函式。 語法:
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
在Python中,queue是一個非常有用的模块。 它提供了多種佇列(queue)實現,用於在多線程環境中安全地交換信息或者數據。 佇列(queue)是一種先進先出(FIFO)的數據結構,允許在佇列的一端插入元素,另一端取出元素。(FIFO 是First In, First Out 的縮寫)
Thumbnail
本文介紹了串列運算式的應用,以及與Lambda匿名函式方法的比較,並提供了程式範例。串列運算式提供了一種簡潔的語法,用於創建、轉換和過濾列表。lambda函式用於創建匿名函式,通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。
Thumbnail
題目 : 28. Find the Index of the First Occurrence in a String