我最近正好奇著大家讀完我的技術文章後的感想,有空的話可以幫我填一下:表單連結

Queue 列隊

跟買電影票一樣,後來的人會排在隊伍後面,先買到票的人,會先離開。

特性
  • 先進先出 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 觀念練習題

以下會提供一系列的運算,請試著回答問題:

  1. 當題目的運算都結束後,queue 內還有幾個項目?
  2. queue 的尾巴(tail)是什麼?
  3. 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)

1
2
3
3 個
notes
phone

LeetCode 練習題

225. Implement Stack using Queues

補充:Dequeue 雙向佇列

也可以寫作 deque,雙向佇列(doubled-ended queue),也是 statck 與 queue 的綜合體。

特性

  • 前後都可以新增元素
  • 前後都可以移除元素
Hash Table(ㄧ)為什麼要有雜湊表? Stack 堆疊

評論

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×