# [資演] 8- Stack 和 Queue ###### tags: `資演` ## 什麼是 stack? Stack (堆疊) 是一種後進先出 (last in first out, **LIFO**) 的資料結構。 ![](https://hackmd.io/_uploads/By7m2xb1q.png) 想像你正在洗一堆盤子。首先,你必須先將盤子從餐桌上疊到洗碗槽裡。此時,先收進來的盤子會疊在這堆盤子的底部,接著一個一個往上疊,最後一個盤子疊在最上面。 現在有了這樣一堆盤子,你要怎麼洗它們呢?一定是從最上面那個盤子開始洗吧!所以,比較晚進來的盤子先處理,這就是後進先出的概念。所以我們可以把一疊盤子當作是一個 stack;或著是說,把一個stack當成是一堆盤子。 類似的概念還有像是一疊便條紙、一疊書等,這些都可以看做是stack在真實生活中的例子。 那麼,我們為什麼需要stack呢? Stack的應用非常廣泛。舉個例子,想想我們瀏覽器的**上一頁**功能(其實書本的上一頁也是類似的)。我們比較早瀏覽的頁面會被放在堆疊的下面,比較晚(也就是說,比較接近**現在**)瀏覽的頁面會被放在堆疊的上面。當我們點擊上一頁按鈕時,我們希望比較接近現在瀏覽的網頁會先呈現給我們,因此這可以用一個stack的資料結構來實現。 ![](https://hackmd.io/_uploads/HkP_fWZyq.png) ## Stack 上的操作 使用Python的list,我們可以很簡單地實作一些stack的功能。 * 創建一個stack 在這裡我們可以直接建立一個空的list,例如: ``` stack = [] ``` * 在stack中加入元素: push 這個功能可以使用list的`append`方法來做,例如: ``` stack.append(3) stack.append(5) stack.append(8) print(stack) ``` 其結果會是`[3, 5, 8]`。 * 把最頂端的元素彈出來: pop Python的list有內建的`pop`方法可以達成這個任務,當我們使用`pop`方法時,會把最後一個元素彈出去,並回傳這個元素。例如: ``` a = stack.pop() ``` 這時`a`會等於`8`,`stack`會變成 `[3, 5]`。 ## 使用 stack 來解決問題 * 檢查括弧是否成對出現 給定一個字串,裡面只包含了三種括弧的字元:`()[]{}`,檢查這些括弧是否有效地成對出現。 ![](https://hackmd.io/_uploads/HyaHhfWy9.png) :::spoiler 提示 從字串的最左邊開始,遇到一個左括號(不論大小),就先append到stack裡面;如果遇到相應的右括號,就把該括號pop出來;或者,當出現了一個右括號,卻沒有相應的左括號能配對,則直接回傳`False`。當整個字串都檢查完後,如果該stack還有東西,代表還有左括號沒有遇到對應的右括號,則回傳`False`;如果stack是空的,則回傳`True`。 ::: :::spoiler 解答 ``` class Solution(object): def isValid(self, s): stack = [] for i in range(len(s)): if (s[i] == "(" or s[i] == "[" or s[i] == "{"): stack.append(s[i]) elif(len(stack) > 0): if(s[i] == ")" and stack[len(stack) - 1] == "("): stack.pop() elif(s[i] == "]" and stack[len(stack) - 1] == "["): stack.pop() elif(s[i] == "}" and stack[len(stack) - 1] == "{"): stack.pop() else: return False else: return False if(len(stack) > 0): return False else: return True ``` ::: ## 什麼是 queue? Queue (佇列) 是一種先進先出 (first in first out, **FIFO**) 的資料結構。 ![](https://hackmd.io/_uploads/H1D7km-yc.png) 想像你正在排隊搶最新的iPhone。很自然地,先到的人可以先買到iPhone。這樣的一個隊伍我們可以稱為是一個queue,因為它滿足了先到先處理的模式。 ## Queue 上的操作 在這邊,我們使用`collections`裡面的`deque`模組來實作queue。這個模組被設計成能快速的從頭尾兩端加入和取出。首先,我們先import這個模組: ``` from collections import deque ``` * 創建一個queue 在這裡我們可以直接建立一個空的list,例如: ``` queue = deque([]) ``` * queue中加入元素: enqueue 這個功能可以使用list的`append`方法來做,例如: ``` queue.append(1) queue.append(3) queue.append(5) print(queue) ``` 其結果會是`deque([1, 3, 5])`。 * 把最前面的元素處理掉: dequeue 在這個模組裡面要取出最前面的元素,也就是dequeue的實作是使用`popleft`方法: ``` a = queue.popleft() ``` 如此一來,我們會得到a是`1`,而`queue`會是`deque([3, 5])`。 ## Circular queue 現在我們來設計一個size固定的circular queue的資料結構。當我們從一個circular queue的最前端取出一個元素之後,這個元素會被append到circular queue的最尾端。 :::spoiler 思路 我們可以使用Python list來實作,並用一個數值`headIndex`來儲存最前面的元素的位置。因為現在的size是固定的,所以我們可以很容易地知道尾端的位置。 ::: :::spoiler 解答 class MyCircularQueue: def __init__(self, k: int): """ Initialize your data structure here. Set the size of the queue to be k. """ self.queue = [0]*k self.headIndex = 0 self.count = 0 self.capacity = k def enQueue(self, value: int) -> bool: """ Insert an element into the circular queue. Return true if the operation is successful. """ if self.count == self.capacity: return False self.queue[(self.headIndex + self.count) % self.capacity] = value self.count += 1 return True def deQueue(self) -> bool: """ Delete an element from the circular queue. Return true if the operation is successful. """ if self.count == 0: return False self.headIndex = (self.headIndex + 1) % self.capacity self.count -= 1 return True def Front(self) -> int: """ Get the front item from the queue. """ if self.count == 0: return -1 return self.queue[self.headIndex] def Rear(self) -> int: """ Get the last item from the queue. """ # empty queue if self.count == 0: return -1 return self.queue[(self.headIndex + self.count - 1) % self.capacity] def isEmpty(self) -> bool: """ Checks whether the circular queue is empty or not. """ return self.count == 0 def isFull(self) -> bool: """ Checks whether the circular queue is full or not. """ return self.count == self.capacity :::
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up