单向队列（数组实现）
package main
import (
"errors"
"fmt"
"os"
)
// 队列是一种重要的数据结构，利用也绝对宽泛，实现队列的形式次要有数组和链表两种形式
// 上面首先应用数组实现一个简略的单向队列
// 队列的信息包含队列的大小、队列的存储模式（数组）、队列的头（不指向第一元素）、队列的尾（指向最初一个元素）// 对列的操作方法次要有向队列增加一个元素、从队列中获取一个元素、显示队列中的元素
// 定义一个构造体用于保留队列的信息
type signalQueue struct {
maxSize int
array [5]int // 模仿队列
head int
tail int
}
// 定义一个向队列增加元素的办法
func (q *signalQueue) Push(val int) error{
// 先判断队列是否已满
if q.tail == q.maxSize - 1 { //tail 含最初一个元素
return errors.New("队列已满")
}
q.tail++ // 向后挪动尾部
q.array[q.tail] = val
return nil
}
// 定义一个从队列获取元素的办法
func (q *signalQueue) Pop() (val int, err error) {
// 判断队列是否为空
if q.tail == q.head {return -1, errors.New("队列为空")
}
q.head++ // 因为 head 指向第一个元素的后面，因而要先向后挪动
val = q.array[q.head]
return val, nil
}
// 定义一个显示队列元素的办法
func (q *signalQueue) List() error {
// 找到队首 ( 不含第一个元素），而后遍历到队尾
for i := q.head + 1; i <= q.tail; i++{fmt.Printf("array[%d]=%d\t", i, q.array[i])
}
fmt.Println()
return nil
}
func main (){
queue := &signalQueue{
maxSize: 5,
array: [5]int{},
head: -1,
tail: -1,
}
var key string
var val int
// 增加数据
for {fmt.Println("1.add 增加数据到队列")
fmt.Println("2.get 从队列获取数据")
fmt.Println("3.show 显示队列")
fmt.Println("4.exit 退出队列")
fmt.Scanln(&key)
switch key {
case "add":
fmt.Println("输出你要入队列的数据")
fmt.Scanln(&val)
err := queue.Push(val)
if err != nil {fmt.Println(err)
} else {fmt.Println("胜利入队")
}
case "get":
val, err := queue.Pop()
if err != nil {fmt.Println(err)
} else {fmt.Println("出队列的数为：", val)
}
case "show":
queue.List()
case "exit":
os.Exit(0)
}
}
}
// 总结：// 下面实现的单向队列存在的一个最大的问题是：// 没有无效的利用数据的无效空间，会存在增加数据显示队列已满，然而获取数据又显示队列为空的状况
// 解决的方法就是将数组的尾部和头部连贯到一起实现一个环形队列即可解决下面的问题 环形队列（数组实现）
package main
import (
"errors"
"fmt"
"os"
)
// 环形队列实现时 head 指向队首第一个元素，tail 指向队尾元素的下一个地位,(空一个地位作为保留)
// 定义一个构造体治理环形队列
type circelQueue struct {
maxSize int
array [5]int
head int
tail int
}
// 定义一个入队列办法
func (q *circelQueue) Push(val int) error {
// 判断是否已满
if q.IsFull(){return errors.New("队列已满")
}
q.array[q.tail] = val
q.tail = (q.tail + 1) % q.maxSize //tail 指向尾部的后一个地位
return nil
}
// 定义一个出队列办法
func (q *circelQueue) Pop() (val int, err error) {
// 判断队列是否为空
if q.IsEmpty(){return -1, errors.New("队列为空")
}
val = q.array[q.head]
q.head = (q.head + 1) % q.maxSize //head 指向下一个元素 ( 下一个队首）return val, nil
}
// 定义一个办法判断环形队列是否已满
func (q *circelQueue) IsFull () bool {return (q.tail + 1) % q.maxSize == q.head
}
// 定义一个办法判断环形队列是否为空
func (q *circelQueue) IsEmpty() bool {return q.tail == q.head}
// 获取环形队列的元素个数
func (q *circelQueue) Size() int {return (q.tail + q.maxSize - q.head) % q.maxSize
}
// 定义一个显示环形队列元素的办法
func (q *circelQueue) List(){
// 判断队列是否为空
if q.Size() == 0 {fmt.Println("队列为空")
}
// 定义一个辅助变量指向 head, 长期 head
tempHead := q.head
for i := 0; i < q.Size(); i++ {fmt.Printf("arr[%d]=%d\t", tempHead, q.array[tempHead])
tempHead = (tempHead + 1) % q.maxSize
}
fmt.Println()}
func main(){
queue := &circelQueue{
maxSize: 5,
array: [5]int{},
head: 0,
tail: 0,
}
var key string
var val int
// 增加数据
for {fmt.Println("1.add 增加数据到队列")
fmt.Println("2.get 从队列获取数据")
fmt.Println("3.show 显示队列")
fmt.Println("4.exit 退出队列")
fmt.Scanln(&key)
switch key {
case "add":
fmt.Println("输出你要入队列的数据")
fmt.Scanln(&val)
err := queue.Push(val)
if err != nil {fmt.Println(err)
} else {fmt.Println("胜利入队")
}
case "get":
val, err := queue.Pop()
if err != nil {fmt.Println(err)
} else {fmt.Println("出队列的数为：", val)
}
case "show":
queue.List()
case "exit":
os.Exit(0)
}
}
}
// 总结：// 环形队列能够解决单向队列没有无效的利用数组无效空间的问题
// 环形队列的实现也合乎大部分利用场景