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

福大大架构师每日一题 · · 799 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

福哥答案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
    }
}

执行结果如下:


image.png

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2020-11-14:手写代码:怎么用数组实现不超过固定大小的队列?

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

799 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传