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～