iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
Software Development

算法30天系列 第 12

Day.12 Queue

Queue(隊列)是一種先進先出(FIFO)的資料結構

平常在超市排隊是一樣,先進來排的人愈早結帳,這觀念很好懂。
在系統的設計上,面對一些大拼發的情境,很常會加入一些Queue的機制,請求都先接下來放到Queue裡面,系統再以自己的速度來消化。
或是Golang的channel,也是隊列的一種應用哦!

以下來實作~
Queue這邊會用鏈結來做,方便我在取完隊列中的第一位,後面的資料都要往前進一位,如果用slice來做,在pop的時候時間複雜度為O(n),但用鏈結的複雜度為O(1)。

程式:

type ListNode struct {
	Data int       
	Next *ListNode 
}

type Queue struct {
	nodes *ListNode
	tail  *ListNode
}

func (q *Queue) Push(val int) {
	if q.nodes == nil {
		q.nodes = &ListNode{
			Data: val,
		}
		q.tail = q.nodes

		return
	}

    // 加在隊列的最後
	q.tail.Next = &ListNode{
		Data: val,
	}
    // 更新最後的節點
	q.tail = q.tail.Next
}

func (q *Queue) Pop() int {
	val := q.nodes.Data
	q.nodes = q.nodes.Next // 第一位移掉

	return val
}

明天來換個主題,講Hash map~


上一篇
Day.11 Decode String
下一篇
Day.13 Hash map
系列文
算法30天30

尚未有邦友留言

立即登入留言