GO语言-数据结构-队列

一边学习一边哭 2022-08-06 08:42:12 阅读数:920

数据结构队列数据语言结构

目录

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或多个元素的线性表。

操作集:

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

1.队列的顺序存储结构

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

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

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

type Queue struct {
front int
rear int
queueArray [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 //队尾下标+1
q.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 //队头下标+1
return v, nil
}

1.5 完整代码

package main
import (
"errors"
"fmt"
)
type Queue struct {
Front int
Rear int
MaxSize int
QueueArray [6]int
}
func main() {
//初始化队列
queue := initQueue()
//队列最大能存储6个元素,最大队尾下标为5
queue.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 //队尾下标+1
q.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 //出队数据置为0
q.Front += 1 //队头下标+1
return 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 //队尾下标+1
q.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 //出队数据置为0
q.Frount += 1 //队头下标+1
return v, nil
}

2.3 循环队列完整代码

package main
import (
"errors"
"fmt"
)
type Queue struct {
Frount int
Rear int
MaxSize int
QueueArray [6]int
}
type QueueNode struct {
}
func main() {
//初始化队列
queue := initQueue()
//队列最大能存储6个元素,最大队尾下标为5
queue.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 //队尾下标+1
q.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 //出队数据置为0
q.Frount += 1 //队头下标+1
return v, nil
}

 

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

 

3.队列的链式存储结构

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

链表的特点是:在链表的头部,做插入、删除操作都方便;在链表的尾部,做插入操作方便,做删除操作不方便。

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

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

//队列-链式存储结构-结构体
type LinkQueue struct {
Frount *QueueNode
Rear *QueueNode
}
//队列-链式存储结构-每个结点结构体
type QueueNode struct {
data int
next *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 = newNode
lq.Rear = newNode
}
//原队尾指向新入队节点
lq.Rear.next = newNode
lq.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 main
import (
"errors"
"fmt"
)
type LinkQueue struct {
Frount *QueueNode
Rear *QueueNode
}
type QueueNode struct {
data int
next *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 = newNode
lq.Rear = newNode
}
//原队尾指向新入队节点
lq.Rear.next = newNode
lq.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
}

 

版权声明:本文为[一边学习一边哭]所创,转载请带上原文链接,感谢。 https://blog.csdn.net/qq522044637/article/details/126158885