数据结构:队列-数组实现
数据结构 About 2,370 words非循环
当head
和tail
索引到最后一位时,队列将无法再使用。
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扫描下方二维码关注公众号和小程序↓↓↓
Loading...