應用題 用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
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
透過蝦皮分潤計畫,輕鬆賺取零用金!本文分享5-6月實測心得,包含數據流程、實際收入、平臺優點及注意事項,並推薦高分潤商品,教你如何運用空閒時間創造被動收入。
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
單身的人有些會養寵物,而我養植物。畢竟寵物離世會傷心,植物沒養好再接再厲就好了~(笑)
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
不知你有沒有過這種經驗?衛生紙只剩最後一包、洗衣精倒不出來,或電池突然沒電。這次一次補貨,從電池、衛生紙到洗衣精,還順便分享使用心得。更棒的是,搭配蝦皮分潤計畫,愛用品不僅自己用得安心,分享給朋友還能賺回饋。立即使用推薦碼 X5Q344E,輕鬆上手,隨時隨地賺取分潤!
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
Thumbnail
身為一個典型的社畜,上班時間被會議、進度、KPI 塞得滿滿,下班後只想要找一個能夠安靜喘口氣的小角落。對我來說,畫畫就是那個屬於自己的小樹洞。無論是胡亂塗鴉,還是慢慢描繪喜歡的插畫人物,那個專注在筆觸和色彩的過程,就像在幫心靈按摩一樣,讓緊繃的神經慢慢鬆開。
Thumbnail
題目會給我們個陣列target,問我們從整數串流中1~n之中,如何透過stack 的 push和pop來模擬生成target指定的形式?
Thumbnail
題目會給我們個陣列target,問我們從整數串流中1~n之中,如何透過stack 的 push和pop來模擬生成target指定的形式?
Thumbnail
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
Thumbnail
題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。 也就是說,要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
Thumbnail
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
Thumbnail
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News