数据结构之队列

阅读目录

一、非环形队列

二、环形队列

1.非环形队列

1.1Golang实现

//非环形队列，数组实现
type UnAreaQueue struct {
    maxSize int
    array [5]int
    front int  //顶部
    rear int  //尾部
}

func (this *UnAreaQueue) AddQueue(val int)(err error){

    // 先判断队列是否已满
    if this.rear == this.maxSize-1{
        return errors.New("queue full")
    }
    // 增加
    this.rear++  // rear后移
    this.array[this.rear] = val
    fmt.Println("this.array:", this.array)
    return
}
// 队列取出数据
func (this *UnAreaQueue) GetQueue()(val int, err error){
    // 先判断是否为空
    if this.rear == this.front{
        return -1,errors.New("queue empty")
    }
    this.front++
    val = this.array[this.front]
    return val, err
}

func (this *UnAreaQueue) ShowQueue(){
    fmt.Println("队列信息如下：")
    // 找到队首遍历到队尾
    for i:=this.front+1;i<=this.rear;i++{
        // this.font不包含队首元素
        fmt.Printf("array[%d]=%d\t", i, this.array[i])
    }
}

func main() {
    // 先创建一个队列
    queue := &UnAreaQueue{maxSize:5, front:-1, rear:-1}
    var key string
    var val int
    for{
        fmt.Println()
        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.AddQueue(val)
            if err != nil{
                fmt.Println(err.Error())
            }else{
                fmt.Println("加入队列成功")
            }
        case "get":
            val, err := queue.GetQueue()
            if err != nil{
                fmt.Println(err.Error())
            }else{
                fmt.Println("从队列中取出的数为：", val)
            }
        case "show":
            queue.ShowQueue()
        case "exit":
            os.Exit(0)
        }
    }

}

2.环形队列

2.1Golang实现

# 创建环形队列结构体
type AreaQueue struct {
    maxSize int
    array [4]int
    head int
    tail int
}
    
func (this *AreaQueue) Show(){
    fmt.Println("环形队列: ")
    // 取出当前队列有多少元素
    size := this.GetSize()
    if size == 0{
        fmt.Println("队列为空")
    }
    //fmt.Println("size=", size)
    flagHead := this.head
    for i:=0;i<size;i++{
        fmt.Printf("array[%d]=%d\t", flagHead, this.array[flagHead])
        flagHead = (flagHead + 1) % this.maxSize
    }
    fmt.Println()
}

func (this *AreaQueue) Push(val int)(err error){
    if this.IsFull(){
        return errors.New("queue full")
    }
    // 添加进去
    this.array[this.tail] = val
    //this.tail++  // 设计思路，tail后加  不计入最后一个数，预留标志位
    this.tail = (this.tail+1) % this.maxSize
    fmt.Println("TAIL:", this.tail)
    return
}

func (this *AreaQueue) Pop()(val int, err error){
    if this.IsEmpty(){
        return -1, errors.New("queue empty")
    }
    // head指向队首 并且包含队首元素
    val = this.array[this.head]
    //this.head++
    this.head = (this.head+1) % this.maxSize
    fmt.Println("HEAD:", this.head)
    return val, err
}
// 判断环形队列full
func(this *AreaQueue) IsFull() bool{
    fmt.Println("tail:",this.tail)
    return (this.tail + 1 ) % this.maxSize == this.head
}
// 判断是否为empty
func(this *AreaQueue) IsEmpty() bool{
    return this.tail == this.head
}
// 取出环形队列有多少元素
func(this *AreaQueue) GetSize() int {
    fmt.Println(this.tail, this.head)
    return (this.tail+this.maxSize-this.head)%this.maxSize
}

func main() {
    // 先创建一个队列
    queue := &AreaQueue{maxSize:4, head:0, tail:0}
    var key string
    var val int
    for{
        fmt.Println()
        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.Show()
        case "exit":
            os.Exit(0)
        }
    }
}