队列介绍

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

非环形的队列数组实现

  1. type Queue struct {
  2.     MaxSize int
  3.     Array [5]int
  4.     Front int // 队列首位
  5.     Real int    // 队列尾部
  6. }

image.png
image.png

代码实现

package main

import (
    "errors"
    "fmt"
    "os"
)

type Queue struct {
    MaxSize int
    Array [5]int
    Front int // 队列首位
    Real int    // 队列尾部
}

func (q *Queue) AddQueue(num int) (err error) {
    if q.Real == (q.MaxSize - 1) {
        return errors.New("队列已满")
    }
    q.Real++
    q.Array[q.Real] = num
    return
}

func (q *Queue) ShowQueue()  {
    for i := q.Front + 1 ; i <= q.Real; i++ {
        fmt.Printf("array[%d] = %d \t \n", i, q.Array[i])
    }
}

func (q *Queue) PopQueue() (num int, err error) {
    if q.Front == q.Real {
        return 0, errors.New("队列为空")
    }
    q.Front++
    num = q.Array[q.Front]
    return
}

func main() {

    queue := &Queue{
        MaxSize: 5,
        Front: -1,
        Real: -1,
    }

    var key string
    var val int
    for  {
        fmt.Printf("1 add \n")
        fmt.Printf("2 get \n")
        fmt.Printf("3 show \n")
        fmt.Printf("4 exit \n")
        fmt.Scanln(&key)
        switch key {
        case "add":
            fmt.Printf("输入 add的值: \n")
            fmt.Scanln(&val)
            err := queue.AddQueue(val)
            if err != nil {
                fmt.Printf("add err : %v \n", err)
            }
            fmt.Printf("add ok \n")
        case "get":
            num, err := queue.PopQueue()
            if err != nil {
                fmt.Printf("pop err : %v \n", err)
            }
            fmt.Printf("get val = %v \n", num)
        case "show":
            queue.ShowQueue()
        case "exit":
            fmt.Printf("exit ok \n")
            os.Exit(0)
        }
    }

}

数组模拟环形队列

分析思路

type CircleQueue struct {
    maxSize int
    arr [5]int
    head int
    tail int
}

  1. 什么时候表示队列满

    (tail + 1) % maxSize == head

  2. 什么时候表示队列空

tail == head

  1. 初始化

tail = 0
head = 0

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

size = (tail + maxSize - head) % maxSize
**

代码实现

package main

import (
    "errors"
    "fmt"
    "os"
)

type CircleQueue struct {
    maxSize int
    arr [5]int
    head int
    tail int
}

func (q *CircleQueue) Push(val int) (err error) {
    if q.IsFull() {
        return errors.New("队列已满!")
    }
    q.arr[q.tail] = val
    q.tail++
    if q.tail == q.maxSize {
        q.tail = 0
    }
    return
}

func (q *CircleQueue) Pop() (val int, err error)  {
    if q.IsEmpty() {
        return 0, errors.New("队列已空")
    }
    val = q.arr[q.head]
    q.head++
    if q.head == q.maxSize {
        q.head = 0
    }
    return
}

func (q *CircleQueue) List() {
    size := q.Size()
    if size == 0 {
        fmt.Printf("队列为空")
        return
    }
    for i := 0; i < q.maxSize; i++ {
        fmt.Printf("arr[%d] = %v \n", i, q.arr[i])

    }
    //for i := q.head; i < q.Size(); i++ {
    //    index := (i + q.maxSize) % q.maxSize
    //    fmt.Printf("arr[%d] = %v \n", index, q.arr[index])
    //}
}

// 是否为空
func (q *CircleQueue) IsFull() (bool) {
    return (q.tail + 1) % q.maxSize == q.head
}

func (q *CircleQueue) IsEmpty() (bool) {
    return q.tail == q.head
}

func (q *CircleQueue) Size() (int) {
    return (q.tail + q.maxSize - q.head) % q.maxSize
}

func main() {
    queue := &CircleQueue{
        maxSize: 5,
        head: 0,
        tail: 0,
    }

    var key string
    var val int
    for  {
        fmt.Printf("1 add \n")
        fmt.Printf("2 get \n")
        fmt.Printf("3 show \n")
        fmt.Printf("4 exit \n")
        fmt.Scanln(&key)
        switch key {
        case "add":
            fmt.Printf("输入 add的值: \n")
            fmt.Scanln(&val)
            err := queue.Push(val)
            if err != nil {
                fmt.Printf("add err : %v \n", err)
            }
            fmt.Printf("add ok \n")
        case "get":
            num, err := queue.Pop()
            if err != nil {
                fmt.Printf("pop err : %v \n", err)
            }
            fmt.Printf("get val = %v \n", num)
        case "show":
            queue.List()
        case "exit":
            fmt.Printf("exit ok \n")
            os.Exit(0)
        }
    }
}