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

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

這題的題目在這裡

題目敘述

題目會給我們一組定義好的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
留言分享你的想法!
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
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
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
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目 Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop
Thumbnail
題目 Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News