2020-11-14：手写代码：怎么用数组实现不超过固定大小的队列？

福大大架构师每日一题 · · 790 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福哥答案2020-11-14：

环形数组即可实现。数组，pull序号，pop序号，长度，容量，需要保存这些信息。

golang代码如下：

package main

import (
    "errors"
    "fmt"
)

/*
怎么用数组实现不超过固定大小的队列？

队列：环形数组
*/
func main() {
    fmt.Println("----------------------")
    if true {
        fmt.Println("定长队列测试")
        stack := NewMyQueue(2)
        fmt.Println(stack.Push(1))
        fmt.Println(stack.Push(2))
        fmt.Println(stack.Push(3))
        fmt.Println("----")
        fmt.Println(stack.Pop())
        fmt.Println(stack.Pop())
        fmt.Println(stack.Pop())
        fmt.Println("\r\n----------------------")
    }
}

type MyQueue struct {
    Arr   []int
    Pushi int
    Popi  int
    Size  int //元素个数
    Limit int //最大容量，值不变
}

func NewMyQueue(l int) *MyQueue {
    ret := &MyQueue{}
    ret.Arr = make([]int, l)
    ret.Pushi = 0
    ret.Popi = 0
    ret.Size = 0
    ret.Limit = l
    return ret
}

func (f *MyQueue) Push(val int) error {
    if f.Size == f.Limit {
        return errors.New("栈满了，不能再加了")
    }
    f.Size++
    f.Arr[f.Pushi] = val
    f.Pushi = f.nextIndex(f.Pushi)
    return nil
}

func (f *MyQueue) Pop() (int, error) {
    if f.Size == 0 {
        return 0, errors.New("栈空了，不能再拿了")
    }
    f.Size--
    ans := f.Arr[f.Popi]
    f.Popi = f.nextIndex(f.Popi)
    return ans, nil
}

func (f *MyQueue) IsEmpty() bool {
    return f.Size == 0
}

//下一个序号，循环着来
func (f *MyQueue) nextIndex(i int) int {
    if i < f.Limit-1 {
        return i + 1
    } else {
        return 0
    }
}

执行结果如下：