目录

1.队列的顺序存储结构

1.1 队列顺序存储结构-结构体定义

1.2 队列顺序存储结构--初始化队列

1.3 队列顺序存储结构-入队

1.4 队列顺序存储结构-出队

1.5 完整代码

2.循环队列

2.1 循环队列-入队

2.2 循环队列-出队

2.3 循环队列完整代码

3.队列的链式存储结构

3.1 队列的链式存储结构-结构体定义

3.2 队列的链式存储结构-队列初始化

3.3 队列的链式存储结构-入队

3.4 队列的链式存储结构-出队

3.5 完整代码

队列（Queue），是具有一定操作限制的线性表。只能在一端插入，在另一端删除。

插入数据：入队（AddQ）删除数据：出队（DeleteQ）先进先出：First In First Out（FIFO）

队列的抽象数据类型描述

数据对象集：一个有0或多个元素的线性表。

操作集：

生成长度为MaxSize的空队列判断队列是否已满判断队列是否已空将元素插入队列中将元素从队列中删除并返回

1.队列的顺序存储结构

队列的顺序存储结构组成：一个一维数组、一个记录队列头元素位置的变量front、一个记录队列尾元素的变量rear。

可以声明front=0，rear=-1。每次入队rear+1，每次出队front+1。rear-front=-1时，队列空。rear+1=MaxSize时，队列满。

1.1 队列顺序存储结构-结构体定义

type Queue struct {frontintrear intqueueArray [6]int}

1.2 队列顺序存储结构--初始化队列

func initQueue() (queue *Queue) {//初始化队列queue = &Queue{front:0,rear: -1,queueArray: [6]int{},}return queue}

1.3 队列顺序存储结构-入队

func (q *Queue) addQueue(v int) error {//判断队列是否已满if q.Rear+1 == q.MaxSize {return errors.New("队列已满")}q.Rear += 1 //队尾下标+1q.QueueArray[q.Rear] = v //数据插入队尾return nil}

1.4 队列顺序存储结构-出队

func (q *Queue) deleteQueue() (int, error) {//判断队列否为空if q.Rear-q.Front == -1 {return -1, errors.New("队列为空")}v := q.QueueArray[q.Front] //获取队列头部元素值q.Front += 1//队头下标+1return v, nil}

1.5 完整代码

package mainimport ("errors""fmt")type Queue struct {FrontintRear intMaxSize intQueueArray [6]int}func main() {//初始化队列queue := initQueue()//队列最大能存储6个元素，最大队尾下标为5queue.addQueue(100)queue.addQueue(200)fmt.Println("入队两个元素")fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Front, queue.Rear)v, err := queue.deleteQueue()if err != nil {fmt.Println(err)} else {fmt.Printf("出队元素: %v, 队头front: %v, 队尾rear: %v\n", v, queue.Front, queue.Rear)}//入队5个元素for i := 1; i <= 5; i++ {err := queue.addQueue(i)if err != nil {fmt.Println(err)}}fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Front, queue.Rear)}//队列初始化func initQueue() (queue *Queue) {//初始化队列queue = &Queue{Front:0,Rear: -1,MaxSize: 6,QueueArray: [6]int{},}return queue}//队列-入队func (q *Queue) addQueue(v int) error {//判断队列是否已满if q.Rear+1 == q.MaxSize {return errors.New("队列已满")}q.Rear += 1 //队尾下标+1q.QueueArray[q.Rear] = v //数据插入队尾return nil}//队列-出队func (q *Queue) deleteQueue() (int, error) {//判断队列否为空if q.Rear-q.Front == -1 {return -1, errors.New("队列为空")}v := q.QueueArray[q.Front] //获取队列头部元素值q.QueueArray[q.Front] = 0 //出队数据置为0q.Front += 1//队头下标+1return v, nil}

2.循环队列

经过多次的入队和出队，队尾会达到数组的限制，而对头会空出几个位置。为了更好地利用数组的空间，则引入循环队列的概念。

可以声明front=0，rear=-1。每次入队rear+1，每次出队front+1。循环存入时，rear和front的值一直累加。需要确定front和rear下标时，使用front和rear与数组MaxSize取模。rear-front=-1时，队列空。rear-front+1=MaxSize时，队列满。

循环队列的实现与常规的使用数组实现的非循环队列的区别就在于，循环队列的出栈和入栈时的队front和rear的操作有所不同。

2.1 循环队列-入队

func (q *Queue) addQueue(v int) error {//判断循环队列是否已满if q.Rear-q.Frount+1 == q.MaxSize {return errors.New("循环队列已满")}q.Rear += 1 //队尾下标+1q.QueueArray[q.Rear%q.MaxSize] = v //数据入队尾;rear与MaxSize去模，获取实际数组下标return nil}

2.2 循环队列-出队

func (q *Queue) deleteQueue() (int, error) {//判断循环队列否为空if q.Rear-q.Frount == -1 {return -1, errors.New("队列为空")}v := q.QueueArray[q.Frount%q.MaxSize] //获取队列头部元素值;front与MaxSize去模，获取实际数组下标q.QueueArray[q.Frount%q.MaxSize] = 0 //出队数据置为0q.Frount += 1//队头下标+1return v, nil}

2.3 循环队列完整代码

package mainimport ("errors""fmt")type Queue struct {FrountintRear intMaxSize intQueueArray [6]int}type QueueNode struct {}func main() {//初始化队列queue := initQueue()//队列最大能存储6个元素，最大队尾下标为5queue.addQueue(100)queue.addQueue(200)fmt.Println("入队两个元素")fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Frount, queue.Rear)v, err := queue.deleteQueue()if err != nil {fmt.Println(err)} else {fmt.Printf("出队元素: %v, 队头front: %v, 队尾rear: %v\n", v, queue.Frount, queue.Rear)}//循环：入队2个元素，出队一个元素fmt.Println("---循环：入队2个元素，出队一个元素---")for i := 1; i <= 5; i++ {fmt.Printf("第%v次循环:\n", i)err := queue.addQueue(i)if err != nil {fmt.Println(err)break}fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Frount, queue.Rear)err = queue.addQueue(i)if err != nil {fmt.Println(err)break}fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Frount, queue.Rear)queue.deleteQueue()fmt.Printf("队列: %v, 队头front: %v, 队尾rear: %v\n", queue.QueueArray, queue.Frount, queue.Rear)}}//队列初始化func initQueue() (queue *Queue) {//初始化队列queue = &Queue{Frount:0,Rear: -1,MaxSize: 6,QueueArray: [6]int{},}return queue}//队列-入队func (q *Queue) addQueue(v int) error {//判断循环队列是否已满if q.Rear-q.Frount+1 == q.MaxSize {return errors.New("循环队列已满")}q.Rear += 1 //队尾下标+1q.QueueArray[q.Rear%q.MaxSize] = v //数据入队尾;rear与MaxSize去模，获取实际数组下标return nil}//队列-出队func (q *Queue) deleteQueue() (int, error) {//判断循环队列否为空if q.Rear-q.Frount == -1 {return -1, errors.New("队列为空")}v := q.QueueArray[q.Frount%q.MaxSize] //获取队列头部元素值;front与MaxSize去模，获取实际数组下标q.QueueArray[q.Frount%q.MaxSize] = 0 //出队数据置为0q.Frount += 1//队头下标+1return v, nil}

如果用非循环队列，数组容量为6，rear为5时就无法再入队元素了。使用了循环队列，只要数组中还有空间，就可以一直循环入队元素。上述例子中rear最终达到了10，也就是一共有11个元素成功入队，充分利用了空间。

3.队列的链式存储结构

队列也可以使用一个单链表实现。插入和删除操作分别在链表的两端进行。

链表的特点是：在链表的头部，做插入、删除操作都方便；在链表的尾部，做插入操作方便，做删除操作不方便。

在链表头部进行出队操作在链表尾部进行入队操作需要front和rear分别指向链的头节点的和尾节点。当front不指向任何节点时，队列为空。

3.1 队列的链式存储结构-结构体定义

//队列-链式存储结构-结构体type LinkQueue struct {Frount *QueueNodeRear *QueueNode}//队列-链式存储结构-每个结点结构体type QueueNode struct {data intnext *QueueNode}

3.2 队列的链式存储结构-队列初始化

func initQueue() (queue *LinkQueue) {//初始化队列queue = &LinkQueue{Frount: nil,Rear: nil,}return queue}

3.3 队列的链式存储结构-入队

func (lq *LinkQueue) addQueue(v int) {//链式存储结构，暂不考虑队列是否已满//新建入队节点newNode := &QueueNode{data: v,next: nil,}//如果Frount为空，表明为入队的第一个节点if lq.Frount == nil {lq.Frount = newNodelq.Rear = newNode}//原队尾指向新入队节点lq.Rear.next = newNodelq.Rear = newNode}

3.4 队列的链式存储结构-出队

func (lq *LinkQueue) deleteQueue() (int, error) {//判断循环队列否为空if lq.Frount == nil {return -1, errors.New("队列为空")}v := lq.Frount.data //获取队列头部元素值lq.Frount = lq.Frount.next //frount指向下一个结点return v, nil}

3.5 完整代码

package mainimport ("errors""fmt")type LinkQueue struct {Frount *QueueNodeRear *QueueNode}type QueueNode struct {data intnext *QueueNode}func main() {//初始化队列queue := initQueue()//循环入队&出队fmt.Println("---入队---")for i := 100; i <= 105; i++ {queue.addQueue(i)fmt.Println("入队元素:", queue.Rear.data)}fmt.Println("---出队---")for queue.Frount != nil {v, err := queue.deleteQueue()if err != nil {fmt.Println(err)} else {fmt.Println("出队元素:", v)}}}//队列初始化func initQueue() (queue *LinkQueue) {//初始化队列queue = &LinkQueue{Frount: nil,Rear: nil,}return queue}//队列-入队func (lq *LinkQueue) addQueue(v int) {//链式存储结构，暂不考虑队列是否已满//新建入队节点newNode := &QueueNode{data: v,next: nil,}//如果Frount为空，表明为入队的第一个节点if lq.Frount == nil {lq.Frount = newNodelq.Rear = newNode}//原队尾指向新入队节点lq.Rear.next = newNodelq.Rear = newNode}//队列-出队func (lq *LinkQueue) deleteQueue() (int, error) {//判断循环队列否为空if lq.Frount == nil {return -1, errors.New("队列为空")}v := lq.Frount.data //获取队列头部元素值lq.Frount = lq.Frount.next //frount指向下一个节点return v, nil}