iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 7
0

經過昨天介紹的 串列 (Linked List),今天來講一個串列的延伸,佇列 (Queue)。佇列一樣有著串列的特性,每一筆元素本身同時包含著下一筆元素的位置。如下:

Memory 0 1 2 3 4 5 6 7
Data 8 14 -7 -2 41 26    
Next 1 2 3 4 5 0    
註:Next 表示下一筆資料的位置,若值為 0 表示沒有下一筆的資料。

 
但佇列有一個特性就是 先進先出 (First In First Out, FIFO),意思就是在一個串列中,先讀取的資料先輸出。這邊假設佇列讀取的方向是由右到左,依序讀入上述的資料。

Queue:

  Head   <---     Tail
          <- 8
        <- 8 14
    <- 8 14 -7
V   <- 8 14 -7 -2
  <- 8 14 -7 -2 41
<- 8 14 -7 -2 41 26
Queue 14 -7 -2 41 26  
Output = [8]
Queue -7 -2 41 26    
Output = [8, 14]
Queue -2 41 26      
Output = [8, 14, -7]

.
.
.

Output = [8, 14, -7, -2, 41, 26]

根據先進先出的特性,資料 8 會先進,所以會先出。再加上串列的特性,資料就會依照串列的順序由 8 持續讀取到 26 ,再從 8 持續輸出到 26 結束。

以上就是 佇列 的介紹。


上一篇
[資料結構] 陣列 (Array) & 串列 (Linked List)
下一篇
[資料結構] 堆疊 (Stack)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言