跟買電影票一樣,後來的人會排在隊伍後面,先買到票的人,會先離開。
特性
- 先進先出 FIFO(first in first out),跟排隊買電影票的概念一樣。
- 元素沒有 index。
- 元素的新增只能從 queue 的後方。
- 元素的移除只能從 queue 的前方。
enqueue
意思是新增項目進 queue,dequeue
意思是移除 queue 內的項目。
使用 Linked List 實作 Stack
在 Queue 的概念中,我們建立的 Linked List 只能使用 push
, shift
方法,不能使用 shift
, unshift
, insertAt
, removeAt
。
要實作的方法:
push:在隊伍後方新增元素
shift:把隊伍前方的元素移除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| const Node = (value) => { return { value, next: null } }
const Queue = () => { let head = null let length = 0 const push = (value) => { let newNode = Node(value) if (head === null) head = newNode else { let currentNode = head while (currentNode.next !== null) { currentNode = currentNode.next } currentNode.next = newNode }
length++ } const shift = () => { if (head === null) return null if (length === 1) { let node = head head = null length = 0 return node } head = head.next length-- }
const printAll = () => { if (head === null) { console.log('Nothing in this linked list') return }
let currentNode = head while (currentNode !== null) { console.log(currentNode.value) currentNode = currentNode.next } }
return { head, length, push, shift, printAll } }
let myQueue = Queue() myQueue.push('Mike') myQueue.push('Harry') myQueue.push('James') myQueue.shift() myQueue.printAll()
|
印出結果:
Harry
James
Queue 觀念練習題
以下會提供一系列的運算,請試著回答問題:
- 當題目的運算都結束後,queue 內還有幾個項目?
- queue 的尾巴(tail)是什麼?
- queue 的頭(head)是什麼?
1 2 3 4 5 6 7 8 9
| enqueue pencil enqueue pen enqueue stapler enqueue phone dequeue dequeue enqueue tablet enqueue notes dequeue
|
答案
最後 stack 會剩下三個元素
(tail) notes tablet phone (head)
LeetCode 練習題
225. Implement Stack using Queues
補充:Dequeue 雙向佇列
也可以寫作 deque,雙向佇列(doubled-ended queue
),也是 statck 與 queue 的綜合體。
特性
評論