應用題 用Queue實作Stack_Leetcode #225 Implement Stack using Queues

應用題 用Queue實作Stack_Leetcode #225 Implement Stack using Queues

更新於 發佈於 閱讀時間約 6 分鐘

這題的題目在這裡

題目敘述

題目會給我們一組定義好的Stack 堆疊的介面,要求底層用兩個或一個Queue來實現。

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


測試範例

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

 


約束條件

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

 Follow-up: Can you implement the stack using only one queue?


演算法

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

其實可以這樣想,既然是FIFO,代表要想盡辦法把剛剛推入最新的元素,把他挪到底層Queue的頭部,這樣下次pop時,才能取到剛剛那筆最新的元素值。

因此,每次插入的時候,除了推入元素之外,還要額外多付出O(n)調整元素位置的成本

例如:
原本是Q[2, 1] 現在,推入3,變成Q[2,1,3]
我們要接著馬上把3調整到Queue的頭部,也就是說,取出2, 1,把他們重新放到3的後面,調整成Q[3,2,1]。

這樣,下次在pop的時候,才能從Queue的頭部取出對應最新的元素值 3


程式碼

from collections import deque

class MyStack:

 def __init__(self):
  """   Initialize your data structure here.   """

# python natively support double-ended queue
  self.queue = deque()
  
  

 def push(self, x: int) -> None:
  """   Push element x onto stack.   """
  
# push new element into queue's tail
  self.queue.append(x)
  
  # make new element on the head position by rotation
  for _ in range(len(self.queue)-1):
   self.queue.append( self.queue.popleft() )
  

 def pop(self) -> int:
  """   Removes the element on top of the stack and returns that element.   """
  
# pop head element of queue
  return self.queue.popleft()
  

 def top(self) -> int:
  """   Get the top element.   """
  
# return head element of queue
  return self.queue[0]
  

 def empty(self) -> bool:
  """   Returns whether the stack is empty.   """
  
  return (not self.queue)



複雜度分析

時間複雜度:

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

push() 在每次呼叫中,會把原本的順序再調整一次,把最新元素從queue的尾巴,調整到queue的頭部,所耗費成本為O(n)

空間複雜度: O(n)

底層queue所耗用最大長度就是元素總數。


關鍵知識點

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

每個元素依照順序推入queue,再從FIFO queue的尾巴,調整移動到FIFO queue的頭部,等價於 stack LIFO的順序


Reference:

[1] Python sol by queue operation. [w/ Comment] - Implement Stack using Queues - LeetCode

avatar-img
小松鼠的演算法樂園
95會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為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
題目會給我們一組定義好的Queue 佇列的介面,要求底層用兩個stack來實現。 也就是說,要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為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