【golang数据结构和算法】

队列跟栈一样， 也是一种操作受限的线性表数据结构，并且具有先进先出的特性。

用数组实现的栈叫作顺序栈， 用链表实现的栈叫作链式栈； 同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

• 顺序队列

package modules

type ArrayQueue struct {
	items []string	// 队列
	n     int       // 队内元素数量
	head  int		// 队内头指针的位置
	tail  int		// 队内尾指针的位置
}
// 构造函数
func (a *ArrayQueue)InitQueue(n int)  {
	a.n = n
	a.head = 0
	a.tail = 0
	a.items = make([]string, a.n)
}

func (a *ArrayQueue)PushQueue(data string) bool {
	if a.tail == a.n {
		if a.head == 0 {
			// tail=n && head=0表示整个队列都已经满了，前后都没有空位置了
			return false
		}
		// 只有tail=0表示队尾已经满了，但队首还有空位置
		// 需要数据搬移，将后面的数据往前移动，为队列腾出位置，然后新入队的数据才能放入队尾
		for i := a.head; i < a.tail; i++ {
			a.items[i-a.head] = a.items[i]
		}
		a.head = 0
		a.tail -= a.head
	}
	// 数据搬移完之后需要更新head和tail指针的位置
	// head指向0位，tail往前移动head个位置；
	a.items[a.tail] = data
	a.tail++
	return true
}

func (a *ArrayQueue)PopQueue() string {
	if a.tail == a.head {
		// 队首指针与队尾指针在同一位置表示队列为空
		return ""
	}
	temp := a.items[a.head]
	// 从head指针部分出队，head后移一位
	a.head++
	return temp
}

package modules

type LinkedQueue struct {
	head *Node
	tail *Node
}

func (l *LinkedQueue)InitLinkedQueue()  {
	l.head = nil
	l.tail = nil
}

func (l *LinkedQueue)PushLinkedQueue(value int)  {
	if l.tail == nil {
		newNode := &Node{Data:value, Next:nil}
		// 当前节点队首既是队尾
		l.head = newNode
		l.tail = newNode
	} else {
		// 新节点从队尾入队
		l.tail.Next = &Node{Data:value, Next:nil}
		// 尾指针后移一位
		l.tail = l.tail.Next
	}
}

func (l *LinkedQueue)PopLinkedQueue() int {
	// 队列为空
	if l.head == nil {
		return -1
	}
	temp := l.head.Data
	l.head = l.head.Next
	if l.head == nil {
		// 只有一个节点时候,出队后队列为空
		l.tail = nil
	}
	return  temp
}