基本介绍

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

栈： 先入后出（弹夹）

队首 ， 队尾
image.png
image.png
数组模拟环形队列

image.png
image.png

使用数组实现简单队列的思路

非环

  1. 创建一个数组arrary，是作为队列的一个字段
  2. front初始化为-1
  3. rear, 表示队列尾部，初始化为-1
  4. 完成队列的基本查找

AddQueue // 加入数据到队列
GetQueue // 从队列取出数据
ShowQueue // 显示队列

代码实现（非环队列）

  1. // 数组模拟队列
  2. // 非环队列
  3. package main
  5. import (
  6.     "errors"
  7.     "fmt"
  8.     "os"
  9. )
  11. /*
  12. 1. 创建一个数组arrary，是作为队列的一个字段
  13. 2. front初始化为-1
  14. 3. rear, 表示队列尾部，初始化为-1
  15. 4. 完成队列的基本查找
  16. AddQueue // 加入数据到队列
  17. GetQueue // 从队列取出数据
  18. ShowQueue // 显示队列
  19. */
  21. type Queue struct {
  22.     maxSize int
  23.     array   [4]int // 数组模拟队列
  24.     front   int    // 队列首(下标index), 不包含队首的元素
  25.     rear    int    // 队列尾(下标index)
  26. }
  28. // 添加数据到队列 - 入队列
  29. func (que *Queue) AddQueue(val int) (err error) {
  30.     // 先判断队列是否已满
  31.     if que.rear == que.maxSize-1 {
  32.         return errors.New("queue full")
  33.     }
  34.     que.rear++ // rear 后移
  35.     que.array[que.rear] = val
  36.     fmt.Println("front = ", que.front, "rear = ", que.rear, "array = ", que.array)
  37.     return
  38. }
  40. // 显示队列
  41. func (que *Queue) ShowQueue() {
  42.     fmt.Println("显示队列: ")
  43.     fmt.Println("front = ", que.front, "rear = ", que.rear, "array = ", que.array)
  44.     // front初始值是 -1， 不包含队首的元素
  45.     for i := que.front + 1; i <= que.rear; i++ {
  46.         fmt.Printf("array[%d] = %d\n", i, que.array[i])
  47.     }
  48.     fmt.Println()
  49. }
  51. // 出队列
  52. func (que *Queue) GetQueue() (val int, err error) {
  53.     // 判断队列是否是空
  54.     if que.rear == que.front {
  55.         return -1, errors.New("queue empty")
  56.     }
  57.     que.front++
  58.     val = que.array[que.front]
  59.     que.array[que.front] = 0
  60.     fmt.Println("front = ", que.front, "rear = ", que.rear, "array = ", que.array)
  61.     return val, err
  62. }
  64. func main() {
  65.     queue := &Queue{
  66.         maxSize: 4,
  67.         front:   -1,
  68.         rear:    -1,
  69.     }
  70.     var key string
  71.     var val int
  72.     for {
  73.         fmt.Println("1. 输入 add 表示添加数据到队列")
  74.         fmt.Println("2. 输入 get 表示从队列中获取数据")
  75.         fmt.Println("3. 输入 show 表示显示队列")
  76.         fmt.Println("4. 输入 exit 表示退出")
  77.         fmt.Scanln(&key)
  78.         switch key {
  79.         case "add":
  80.             fmt.Println("请输入要入队列的数")
  81.             fmt.Scanln(&val)
  82.             err := queue.AddQueue(val)
  83.             if err == nil {
  84.                 fmt.Println("加入队列成功")
  85.             } else {
  86.                 fmt.Println(err.Error())
  87.             }
  88.         case "get":
  89.             val, err := queue.GetQueue()
  90.             if err == nil {
  91.                 fmt.Println("取到的值：", val)
  92.             } else {
  93.                 fmt.Println(err.Error())
  94.             }
  95.         case "show":
  96.             queue.ShowQueue()
  97.         case "exit":
  98.             os.Exit(0)
  99.         default:
  100.             fmt.Println("输入有误，请重新输入")
  101.         }
  102.     }
  103. }
  105. /*
  106. get
  107. front =  2 rear =  3 array =  [0 0 0 4]
  108. 取到的值： 3
  109. 1. 输入 add 表示添加数据到队列
  110. 2. 输入 get 表示从队列中获取数据
  111. 3. 输入 show 表示显示队列
  112. 4. 输入 exit 表示退出
  113. get
  114. front =  3 rear =  3 array =  [0 0 0 0]
  115. 取到的值： 4
  116. 1. 输入 add 表示添加数据到队列
  117. 2. 输入 get 表示从队列中获取数据
  118. 3. 输入 show 表示显示队列
  119. 4. 输入 exit 表示退出
  120. get
  121. queue empty
  122. */

数组模拟环形队列

分析思路:

  1. 什么时候表示队列满

    (tail + 1) % maxSize = head

  2. tail == head 表示空

  3. 初始化时， tail = 0 head = 0
  4. 环形实现： tail = (tail + 1) % maxSize, head = (head + 1) % maxSize

核心思想：到达队尾的时候，通过 加1取模 的方式回到队首

  1. 怎么统计该队列有多少个元素

(tail + maxSize - head ) % maxSize

注意： 数组的长度比实际存储的长度多1

代码实现

  1. // 数组模拟环形队列(有缺口)
  2. package main
  4. import (
  5.     "errors"
  6.     "fmt"
  7.     "os"
  8. )
  10. /*
  11. 分析思路:
  12. 1. 什么时候表示队列满
  13.  (tail + 1) % maxSize == head
  14. 2. tail == head 表示空
  15. 3. 初始化时， tail = 0 head = 0
  16. 4. 怎么统计该队列有多少个元素
  17. (tail + maxSize - head ) % maxSize
  18. */
  20. type CircleQueue struct {
  21.     maxSize int
  22.     array   [5]int
  23.     head    int // 队首， 初始 0
  24.     tail    int // 队尾， 初始 0
  25. }
  27. // 判断环形队列是否已满
  28. func (que *CircleQueue) IsFull() bool {
  29.     fmt.Println("IsFull --- head", que.head, "tail", que.tail)
  30.     return (que.tail+1)%que.maxSize == que.head
  31. }
  33. // 判断环形队列是否为空
  34. func (que *CircleQueue) IsEmpty() bool {
  35.     return que.tail == que.head
  36. }
  38. // 环形队列所有元素
  39. func (que *CircleQueue) Size() int {
  40.     return (que.tail + que.maxSize - que.head) % que.maxSize
  41. }
  43. // 入队列
  44. func (que *CircleQueue) Push(val int) (err error) {
  45.     // 先判断队列是否已满
  46.     if que.IsFull() {
  47.         return errors.New("CircleQueue full")
  48.     }
  49.     que.array[que.tail] = val
  50.     fmt.Println("head = ", que.head, "tail = ", que.tail, "array = ", que.array)
  51.     // que.tail = (que.tail + 1) % que.maxSize
  52.     que.tail = (que.tail + 1) % len(que.array)
  53.     // que.tail++ // tail 后移
  54.     return
  55. }
  57. // 出队列
  58. func (que *CircleQueue) Pop() (val int, err error) {
  59.     // 判断队列是否是空
  60.     if que.IsEmpty() {
  61.         return 0, errors.New("CircleQueue empty")
  62.     }
  63.     val = que.array[que.head]
  64.     que.array[que.head] = 0
  65.     fmt.Println("Pop --- head = ", que.head, "tail = ", que.tail, "array = ", que.array)
  66.     que.head = (que.head + 1) % que.maxSize
  67.     return val, err
  68. }
  70. // 显示队列
  71. func (que *CircleQueue) ShowQueue() {
  72.     fmt.Println("显示队列: ")
  73.     size := que.Size()
  74.     if size == 0 {
  75.         fmt.Println("队列为空")
  76.     }
  78.     tempHead := que.head
  79.     for i := 0; i < size; i++ {
  80.         fmt.Printf("arr[%d]=%d\t", tempHead, que.array[tempHead])
  81.         tempHead = (tempHead + 1) % que.maxSize
  82.     }
  83.     fmt.Println()
  84.     fmt.Println("head = ", que.head, "tail = ", que.tail, "array = ", que.array)
  85.     fmt.Println()
  86. }
  88. func main() {
  89.     circleQueue := &CircleQueue{
  90.         maxSize: 5,
  91.         head:    0,
  92.         tail:    0,
  93.     }
  94.     var key string
  95.     var val int
  96.     for {
  97.         fmt.Println("1. 输入 add 表示添加数据到队列")
  98.         fmt.Println("2. 输入 get 表示从队列中获取数据")
  99.         fmt.Println("3. 输入 show 表示显示队列")
  100.         fmt.Println("4. 输入 exit 表示退出")
  101.         fmt.Scanln(&key)
  102.         switch key {
  103.         case "add":
  104.             fmt.Println("请输入要入队列的数")
  105.             fmt.Scanln(&val)
  106.             err := circleQueue.Push(val)
  107.             if err == nil {
  108.                 fmt.Println("加入队列成功")
  109.             } else {
  110.                 fmt.Println(err.Error())
  111.             }
  112.         case "get":
  113.             fmt.Println("取出")
  114.             val, err := circleQueue.Pop()
  115.             if err == nil {
  116.                 fmt.Println("取到的值：", val)
  117.             } else {
  118.                 fmt.Println(err.Error())
  119.             }
  120.         case "show":
  121.             circleQueue.ShowQueue()
  122.         case "exit":
  123.             os.Exit(0)
  124.         default:
  125.             fmt.Println("输入有误，请重新输入")
  126.         }
  127.     }
  128. }
  130. /*
  131. get
  132. 取出
  133. Pop --- head =  1 tail =  0 array =  [0 0 3 4 5]
  134. 取到的值： 2
  135. 1. 输入 add 表示添加数据到队列
  136. 2. 输入 get 表示从队列中获取数据
  137. 3. 输入 show 表示显示队列
  138. 4. 输入 exit 表示退出
  139. add
  140. 请输入要入队列的数
  141. 6
  142. IsFull --- head 2 tail 0
  143. head =  2 tail =  0 array =  [6 0 3 4 5]
  144. 加入队列成功
  145. 1. 输入 add 表示添加数据到队列
  146. 2. 输入 get 表示从队列中获取数据
  147. 3. 输入 show 表示显示队列
  148. 4. 输入 exit 表示退出
  149. show
  150. 显示队列:
  151. arr[2]=3        arr[3]=4        arr[4]=5        arr[0]=6
  152. head =  2 tail =  1 array =  [6 0 3 4 5]
  153. */