数据结构:队列-数组实现

数据结构 About 2,370 words

非循环

headtail索引到最后一位时,队列将无法再使用。

func main() {
    queue := &ArrayQueue{arr: make([]int, 3)}
    queue.Add(1)
    queue.Add(2)
    queue.Add(3)
    queue.Get()
    queue.Get()
    queue.ShowQueue()
    fmt.Println("queue size#", queue.Size())

}

type ArrayQueue struct {
    head int
    tail int
    arr  []int
}

func (queue *ArrayQueue) IsFull() bool {
    return queue.tail == len(queue.arr)
}

func (queue *ArrayQueue) IsEmpty() bool {
    return queue.head == queue.tail
}

func (queue *ArrayQueue) Add(element int) {
    if queue.IsFull() {
        panic("队列已满,无法加入")
    }
    queue.arr[queue.tail] = element
    queue.tail++
}

func (queue *ArrayQueue) Get() int {
    if queue.IsEmpty() {
        panic("队列为空,无法获取")
    }
    defer func() {
        queue.head++
    }()
    return queue.arr[queue.head]
}

func (queue *ArrayQueue) Size() int {
    return queue.tail - queue.head
}

func (queue *ArrayQueue) ShowQueue() {
    if queue.IsEmpty() {
        return
    }
    for i := queue.head; i < queue.tail; i++ {
        fmt.Println(queue.arr[i])
    }
}

循环

空出数组最后一个位置,即初始化数组长度为3,则队列实际可用长度为2

func main() {
    queue := &CircleArrayQueue{arr: make([]int, 3)}
    queue.Add(1)
    queue.Add(2)
    queue.Get()
    queue.Get()
    queue.Add(3)
    queue.Add(4)
    queue.ShowQueue()
    fmt.Println("circle queue size#", queue.Size())
}

type CircleArrayQueue struct {
    head int
    tail int
    arr  []int
}

func (queue *CircleArrayQueue) IsFull() bool {
    return (queue.tail+1)%len(queue.arr) == queue.head
}

func (queue *CircleArrayQueue) IsEmpty() bool {
    return queue.head == queue.tail
}

func (queue *CircleArrayQueue) Add(element int) {
    if queue.IsFull() {
        panic("队列已满,无法加入")
    }
    queue.arr[queue.tail] = element
    queue.tail = (queue.tail + 1) % len(queue.arr)
}

func (queue *CircleArrayQueue) Get() int {
    if queue.IsEmpty() {
        panic("队列为空,无法获取")
    }
    defer func() {
        queue.head = (queue.head + 1) % len(queue.arr)
    }()
    return queue.arr[queue.head]
}

func (queue *CircleArrayQueue) Size() int {
    return (queue.tail + len(queue.arr) - queue.head) % len(queue.arr)
}

func (queue *CircleArrayQueue) ShowQueue() {
    if queue.IsEmpty() {
        return
    }
    for i := queue.head; i < queue.head+queue.Size(); i++ {
        fmt.Println(queue.arr[i%len(queue.arr)])
    }
}
Views: 1,810 · Posted: 2021-01-18

————        END        ————

Give me a Star, Thanks:)

https://github.com/fendoudebb/LiteNote

扫描下方二维码关注公众号和小程序↓↓↓

扫描下方二维码关注公众号和小程序↓↓↓


Today On History
Browsing Refresh