Golang 数组模拟队列

Jackey Golang 477 次浏览 , 没有评论

结构体定义

type Queue struct {
  maxSize int // 队列的最大长度
  array []int // 存放队列数组
  head int // 指向队列队首 默认值 0
  tail int // 指向队列队尾 默认值 0
}

分析:

  1. 什么时候队列满?(tail + 1) % maxSize == head
  2. tail == head 表示队列为空
  3. 初始化时,head = tail = 0
  4. 怎么统计队列有多少个元素?(tail + maxSize – head) % maxSize

代码实现

package main

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

type Queue struct {
  maxSize int    // 队列的最大长度
  array   [5]int // 存放队列数组
  head    int    // 指向队列队首 默认值 0
  tail    int    // 指向队列队尾 默认值 0
}

// 入队列
func (q *Queue) Push(val int) (err error) {
  if q.IsFull() {
    return errors.New("queue is full")
  }

  // q.tail 在队列尾部,但是不包含最后一个元素
  q.array[q.tail] = val
  q.tail = (q.tail + 1) % q.maxSize
  return
}

// 出队列
func (q *Queue) Pop() (val int, err error) {
  if q.IsEmpty() {
    return 0, errors.New("queue is empty")
  }
  // q.head 指向队列队首,并且包含首元素
  val = q.array[q.head]
  q.head = (q.head + 1) % q.maxSize
  return val, nil
}

// 显示队列
func (q *Queue) List() {
  fmt.Println("队列详情如下:")

  // 取出当前队列有多少个元素
  size := q.Size()
  if size == 0 {
    fmt.Println("队列为空")
    return
  }

  // 设计一个辅助变量指向head
  temp := q.head
  for i := 0; i < size; i++ {
    fmt.Printf("array[%d]=%d\n", temp, q.array[temp])
    temp = (temp + 1) % q.maxSize
  }
  fmt.Println()
}

// 判断队列是否为满
func (q *Queue) IsFull() bool {
  return (q.tail+1)%q.maxSize == q.head
}

// 判断队列是否为空
func (q *Queue) IsEmpty() bool {
  return q.tail == q.head
}

// 获取队列有多少个元素
func (q *Queue) Size() int {
  return (q.tail + q.maxSize - q.head) % q.maxSize
}

func main() {
  queue := Queue{
    maxSize: 5,
    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.Error())
      } else {
        fmt.Println("加入队列成功")
      }
    case "get":
      val, err := queue.Pop()
      if err != nil {
        fmt.Println(err.Error())
      } else {
        fmt.Println("从队列中取出一个数=", val)
      }
    case "show":
      queue.List()
    case "exit":
      os.Exit(0)
    }
  }
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

Go