基本介绍

队列是一个有序的列表，可以用数组或者链表来实现。
队列遵循先进先出的原则，即先存入队列的数据先取出，后存入的数据后取出。

单向队列

image.png

代码如下：

  1. package main
  3. import (
  4.     "errors"
  5.     "fmt"
  6. )
  8. type Queue struct {
  9.     maxSize int
  10.     queue   [5]int // 模拟队列
  11.     front   int    // 队首
  12.     rear    int    // 队尾
  13. }
  15. func (q *Queue) AddQueue(num int) (err error) {
  16.     // 当队尾在最后就不能再加入了
  17.     if q.rear == q.maxSize-1 {
  18.         err = errors.New("队列已满")
  19.         return
  20.     }
  21.     q.rear++
  22.     q.queue[q.rear] = num
  23.     return
  24. }
  26. func (q *Queue) ShowQueue() {
  27.     // 找到队首，遍历到队尾
  28.     for i := q.front + 1; i <= q.rear; i++ {
  29.         fmt.Printf("queue[%d]=%d\n", i, q.queue[i])
  30.     }
  31. }
  33. func (q *Queue) GetQueue() (err error) {
  34.     // 如果队列为空，则取不出数据
  35.     if q.rear == q.front {
  36.         err = errors.New("队列为空")
  37.         return err
  38.     }
  39.     q.front ++
  40.     fmt.Printf("出队列的数为：%d\n",q.queue[q.front])
  41.     return
  42. }
  44. func main() {
  45.     // 初始化
  46.     queue := Queue{
  47.         maxSize: 5,
  48.         queue:   [5]int{},
  49.         front:   -1,
  50.         rear:    -1,
  51.     }
  52.     for {
  53.         fmt.Println("====================")
  54.         fmt.Println("输入add 添加数据到队列")
  55.         fmt.Println("输入get 从队列获取数据")
  56.         fmt.Println("输入show 查询队列消息")
  57.         fmt.Println("====================")
  58.         var key string
  59.         var value int
  60.         fmt.Print("请输入选择：")
  61.         _, _ = fmt.Scanln(&key)
  62.         switch key {
  63.         case "add":
  64.             fmt.Print("请输入需要添加的数据：")
  65.             _, _ = fmt.Scanln(&value)
  66.             err := queue.AddQueue(value)
  67.             if err != nil {
  68.                 fmt.Println(err)
  69.             }
  70.         case "get":
  71.             fmt.Println("")
  72.             err := queue.GetQueue()
  73.             if err != nil {
  74.                 fmt.Println(err)
  75.             }
  76.         case "show":
  77.             fmt.Println("查看队列消息")
  78.             queue.ShowQueue()
  79.         default:
  80.             fmt.Println("选择错误")
  81.         }
  82.     }
  83. }

环形队列

思路：

  1. 当(tail + 1) % maxSize == head的时候队列满
  2. tail == head 表示队列为空
  3. 初始化时，tail =0 head = 0
  4. 统计队列元素：(tail + maxSize - head) % maxSize