队列

一、什么是队列
1. 定义：队列是只允许在一端（队头）删除，在另一端（队尾）插入的线性表。
2. 特性：先进先出。

图示：

二、队列的应用
1. 在程序设计中，凡是要按照先来先处理的原则操作的问题都可以利用队列来解决。
2. 打印缓冲。
3. 分时系统的管理。

三、队列的实现
队列可使用数组或单向线性链表实现，下面分别是这两种实现方式的Go语言代码。
1. 数组队列

/**
* 数组队列
* author：JetWu
* date：2020.02.03
 */
package arrayQueue

import (
	"errors"
	"fmt"
)

/**
* 数组队列结构
**/
type ArrayQueue struct {
	slice []int
	tail  int //队尾位置：slice最后一个有效元素的索引位置
}

/**
* 创建空队列
**/
func NewArrayQueue() *ArrayQueue {
	return &ArrayQueue{
		slice: make([]int, 10),
		tail:  -1,
	}
}

/**
* 使用切片创建队列
**/
func MakeArrayQueue(slice []int) *ArrayQueue {
	return &ArrayQueue{
		slice: slice,
		tail:  len(slice) - 1,
	}
}

/**
* 打印队列
**/
func (aq *ArrayQueue) Print() {
	fmt.Println("count:")
	fmt.Println(aq.Count())
	fmt.Println("members:")
	for i := 0; i <= aq.tail; i++ {
		fmt.Print(aq.slice[i], " ")
	}
	fmt.Println()
}

/**
* 判断队列是否为空
**/
func (aq *ArrayQueue) IsEmpty() bool {
	return aq.tail == -1
}

/**
* 队列长度
**/
func (aq *ArrayQueue) Count() int {
	return aq.tail + 1
}

/**
* 入列
**/
func (aq *ArrayQueue) Push(data int) bool {
	aq.tail++
	if aq.tail+1 <= len(aq.slice) {
		aq.slice[aq.tail] = data
	} else {
		aq.slice = append(aq.slice, data)
	}
	return true
}

/**
* 出列
**/
func (aq *ArrayQueue) Pop() (int, error) {
	if aq.tail < 0 {
		return 0, errors.New("队列为空")
	}
	data := aq.slice[0]
	for i := 1; i <= aq.tail; i++ { //所有元素前移一个位置
		aq.slice[i-1] = aq.slice[i]
	}
	aq.tail--
	return data, nil
}

2. 链表队列

/**
* 链表队列
* author：JetWu
* date：2020.02.03
 */
package listQueue

import (
	"errors"
	"fmt"
)

/**
* 链表队列节点结构
**/
type node struct {
	data int
	next *node
}

/**
* 链表队列结构
**/
type ListQueue struct {
	head *node //队头
	tail *node //队尾：方便插入，避免遍历
}

/**
* 创建空队列
**/
func NewListQueue() *ListQueue {
	nod := &node{next: nil}
	return &ListQueue{
		head: nod,
		tail: nod,
	}
}

/**
* 使用切片创建队列
**/
func MakeListQueue(slice []int) *ListQueue {
	lq := NewListQueue()
	for i := 0; i < len(slice); i++ {
		lq.Push(slice[i])
	}
	return lq
}

/**
* 打印队列
**/
func (lq *ListQueue) Print() {
	count := 0
	ptr := lq.head.next
	fmt.Println("members:")
	for ptr != nil {
		fmt.Print(ptr.data, " ")
		count++
		ptr = ptr.next
	}
	fmt.Println()
	fmt.Println("count:")
	fmt.Println(count)
}

/**
* 判断队列是否为空
**/
func (lq *ListQueue) IsEmpty() bool {
	return ls.head == ls.tail
}

/**
* 队列长度
**/
func (lq *ListQueue) Count() int {
	count := 0
	ptr := lq.head.next
	for ptr != nil {
		count++
		ptr = ptr.next
	}
	return count
}

/**
* 入列
**/
func (lq *ListQueue) Push(data int) bool {
	nod := node{data: data, next: nil}
	lq.tail.next = &nod
	lq.tail = &nod
	return true
}

/**
* 出列
**/
func (lq *ListQueue) Pop() (int, error) {
	if lq.head.next == nil {
		return 0, errors.New("队列为空")
	}
	data := lq.head.next.data
	lq.head.next = lq.head.next.next
	if lq.head.next == nil {
		lq.tail = lq.head
	}
	return data, nil
}

注：这里队列存储int类型数据，存储其他类型元素可依理类推。