什么是队列
关于什么是栈, 我们可以先看百度百科给的解释
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表. 进行插入操作的端称为队尾，进行删除操作的端称为队头
你如果不能理解，暂时可以把它理解为一个拥有排队秩序的栈, 像是一根水管
队列讲究的是先进先出，比如你在食堂打饭，肯定是队头的人先打饭.
那么进行插入操作的入口,我们称之为队尾
进行删除操作的出口我们称之为队首
Go+定义队列
实现结构
现在我们来实现出队列 的数据结构
- 要设计队列, 我们需要需要有一个变量判断队列的容量大小.
- 我们要有变量来限制队列的最大容量
- 一个指向队列的头 front 的变量
- 一个指向队列的尾 rear的变量
// 定义队列的结构体 type Queue struct { // 用来装元素的切片 queueSet []string // 队首标记位 front int // 队尾标记位 rear int // 队列的容量 queueSize int } // 初始化时，要传入容量限制 func NewQueue(QueueMaxSize int) *Queue { return &Queue{ queueSet: make([]string, QueueMaxSize ), // 在队列中已经装了多少元素我们可以用queueSize表示 front: 0, rear: 0, queueSize: 0, } }
请注意这里的, queueSize 是用来判断的,即可用容量, queueSet: make([]string, QueueMaxSize) 里的 QueueMaxSize 是整个队列的最大容量
队列的基本操作
思想
队列的基本操作包括如下几种
判断队列是否为空： 若队列为空则返回 true，否则返回 false
判断队列是否已满： 若队列为满则返回 true，否则返回 false
入队操作： 在队列的队尾插入元素
出队操作： 将队头元素出队，并返回出元素值
判断队列是否为空
// 判断队列是否为空 func (q *Queue) IsEmpty() bool { // 判断容量大小 if q.queueSize == 0 { return true } return false }
判断队列是否已满
// 判断队列是否已满 func (q *Queue) IsFull() bool { if q.queueSize == len(q.queueSet) { return true } return false }
入队
// 队尾入队 func (q *Queue) Push(element string) bool { // 判断队列是否已满 if q.IsFull() { return false } // 入队 q.queueSet[q.rear] = element // 队尾地址和容量+1 q.rear++ q.queueSize++ return true }
出队
// 队首出队 func (q *Queue) Pop() (bool, string) { // 判断队列是否为空 if q.IsEmpty() { return false, "null" } // 获取队首位置数据 ret := q.queueSet[q.front] // 队首+1，容量-1 q.front++ q.queueSize-- return true, ret }
完整案例
package main // 定义队列的结构体 type Queue struct { // 用来装元素的切片 queueSet []string // 队首标记位 front int // 队尾标记位 rear int // 队列的容量 queueSize int } // 初始化时，要传入容量限制 func NewQueue(QueueMaxSize int) *Queue { return &Queue{ queueSet: make([]string, QueueMaxSize ), // 在队列中已经装了多少元素我们可以用queueSize表示 front: 0, rear: 0, queueSize: 0, } } // 判断队列是否为空 func (q *Queue) IsEmpty() bool { // 判断容量大小 if q.queueSize == 0 { return true } return false } // 判断队列是否已满 func (q *Queue) IsFull() bool { if q.queueSize == len(q.queueSet) { return true } return false } // 队尾入队 func (q *Queue) Push(element string) bool { // 判断队列是否已满 if q.IsFull() { return false } // 入队 q.queueSet[q.rear] = element // 队尾地址和容量+1 q.rear++ q.queueSize++ return true } // 队首出队 func (q *Queue) Pop() (bool, string) { // 判断队列是否为空 if q.IsEmpty() { return false, "null" } // 获取队首位置数据 ret := q.queueSet[q.front] // 队首+1，容量-1 q.front++ q.queueSize-- return true, ret } func main() { // 初始化队列 queue := NewQueue(2) // 入队 queue.Push("您好，我是uiu") queue.Push("我的网站是：uiuing.com") // 出队 println queue.Pop() println queue.Pop() // 检查队列空的情况下能否继续删除 println queue.Pop() }
运行结果
思考
经测试，队列已经可正常的运行了，但我们在每次让元素出队的时候，队列的头指针是不断的在往后移。当队头指向的索引值比我们的容器长度还要大，那种情况出现的时候要怎么办呢？
不只是这种情况，看如下的情况
// 初始化队列 queue := NewQueue(2) println "-------空队列-------" println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------入队+出队一次-------" queue.Push("您好，我是uiu") queue.Pop() println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------入队+出队一次-------" queue.Push("我的网站是：uiuing.com") queue.Pop() println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------这将会引起错误-------" queue.Push("我的网站是：uiuing.com")
为什么会出现这个错误信息呢?
你仔细看能看出, 在初始化容量为2的情况下, 执行两次入队+出队操作之后,容量确实为0,但是却存储不进, 发生了越界的情况, 这是因为在rear为2的情况下, 在队列中再无法添加, 这就导致了资源的浪费.
那既然在使用过程中，front 和 rear 都只能往后移导致有用的空间被浪费了，那么我们可以去做一个可以再利用，不浪费一点空间的队列呢？
也就是我们可以做一个循环队列
循环队列，顾名思义，它长得像一个环, 原本数组是有头有尾的，是一条直线, 现在我们把首尾相连.
像不像一根圆形的水管, 在设定的最大容量之类,空间可循环利用
实现循环队列
思想
我们假设循环队列里目前 **front **在索引 2， rear 在索引 6，那么新的元素入队时，新元素将被加入到索引 0 的位置。
这在上面的队列中是会出现错误的,因为并不循环,一旦但当queueSize=6的时候,是会出现数组越界情况的
我们得存储到0里去, 通过这样的方法,实现循环队列，我们成功避免了数据搬移操作, 看起来不难理解，我们接下来要弄清楚两件事情
- 判断队列是否为空和是否为满,
- 让两个指针可以在堆里中循环起来.
判断队列状态
思想
我们之所以要用 queueSize 表示队列的实际长度，而不是rear - front就是为了循环队列
在循环时，rear 和 front 是不能比较的，我们独立出来一个queueSize 就不会出现这种问题，因为只有入队操作才会让 queueSize + 1， 也只有出队操作能让 queueSize - 1, 所以这里我们的判断队列状态的函数可以直接不变就拿来使用.
判断是否为空
// 检查循环队列是否为空 func (this *Queue) IsEmpty() bool { if this.queueSize == 0 { return true } return false }
判断是否已满
// 检查循环队列是否已满 func (this *Queue) IsFull() bool { if this.queueSize == len(this.queueSet ) { return true } return false }
计算索引
思想
解决了判断状态问题，我们可以继续解决索引值的计算问题了.
入队操作
在入队时. 我们只要对 rear 先对队列的容量取余 ，计算出的索引值就是我们要插入的位置.
出队操作
要出队的元素是 front 对队列容量取余所指向的元素，取出之后下一个 front 的值需要先对队列的容量取余再加 1
入队
// 入队操作 func (this *Queue) Push(value string) bool { // 排除结构体为空 或者 队列为满的情况 if this.queueSet == nil || this.IsFull() { return false } // 对 rear 先对队列的容量取余 this.queueSet[this.rear%len(this.queueSet )] = value // rear位置取余量后 + 1 this.rear = this.rear%len(this.queueSet ) + 1 // queueSize大小 + 1 this.queueSize++ return true }
出队
// 出队操作 func (this *Queue) Pop() (bool, string) { // 排除结构体为空 或者 队列为空的情况 if this.queueSet == nil || this.IsEmpty() { return false, "null" } // 求出 front 对队列容量取余所指向的元素 ret := this.queueSet[this.front%len(this.queueSet )] // 对 front 重新定位 this.front = this.front%len(this.queueSet ) + 1 // queunSize大小 - 1 this.queueSize-- return true, ret }
完整案例
/ 定义队列的结构体 type Queue struct { // 用来装元素的切片 queueSet []string // 队首标记位 front int // 队尾标记位 rear int // 队列的容量 queueSize int } // 初始化时，要传入容量限制 func NewQueue(QueueMaxSize int) *Queue { return &Queue{ queueSet: make([]string, QueueMaxSize ), // 在队列中已经装了多少元素我们可以用queueSize表示 front: 0, rear: 0, queueSize: 0, } } // 检查循环队列是否为空 func (this *Queue) IsEmpty() bool { if this.queueSize == 0 { return true } return false } // 检查循环队列是否已满 func (this *Queue) IsFull() bool { if this.queueSize == len(this.queueSet) { return true } return false } // 入队操作 func (this *Queue) Push(value string) bool { // 排除结构体为空 或者 队列已满的情况 if this.queueSet == nil || this.IsFull() { return false } // 对 rear 先对队列的容量取余 this.queueSet[this.rear%len(this.queueSet)] = value // rear位置取余量后 + 1 this.rear = this.rear%len(this.queueSet) + 1 // queueSize大小 + 1 this.queueSize++ return true } // 出队操作 func (this *Queue) Pop() (bool, string) { // 排除结构体为空 或者 队列为空的情况 if this.queueSet == nil || this.IsEmpty() { return false, "null" } // 求出 front 对队列容量取余所指向的元素 ret := this.queueSet[this.front%len(this.queueSet)] // 对 front 重新定位 this.front = this.front%len(this.queueSet) + 1 // queunSize大小 - 1 this.queueSize-- return true, ret } func main() { // 初始化队列 queue := NewQueue(2) println "-------空队列-------" println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------入队+出队一次-------" queue.Push("您好，我是uiu") queue.Pop() println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------入队+出队一次-------" queue.Push("我的网站是：uiuing.com") queue.Pop() println "front: ", queue.front println "rear: ", queue.rear println "queueSize: ", queue.queueSize println "-------在循环队列中并不会产生这样的错误-------" queue.Pop() }
