手把手教媳妇 用顺序存储实现一个简单的队列

首先了解下队列的基本概念，队列属于一种在一端进行插入在另一端进行删除或者说获取元素的特殊形式的线性表，和栈刚好相反，栈则是只能在一端进行插入，删除或者获取的线性表，下面用简单的顺序存储的方式来实现一个基本的队列的功能，先附上算法分析图

微信图片_20200630155613.png

package ds

import (
    "errors"
)

type Queue interface {
    Add(element interface{}) error
    Poll() (interface{}, error)
}

type DQueue struct {
    front int
    rear  int
    list  []interface{}
}

//入队操作
func (q *DQueue) Add(el interface{}) error {

    // 判断队列是否已满
    if q.rear+1 == q.front || (q.front == -1 && q.rear == len(q.list)-1) {
        return errors.New("队列已经满,无法存储")
    }

    //解决假性溢出问题
    if q.rear+1 >= len(q.list) {
        q.rear = (q.rear + 1) % len(q.list)
    } else {
        q.rear += 1
    }
    //存放数据到队列
    q.list[q.rear] = el
    return nil

}

//出队操作
func (q *DQueue) Poll() (interface{}, error) {

    //判断是否是空队列
    if q.front == q.rear {
        return nil, errors.New("队列为空，没有数据")
    }
    //解决假性溢出问题
    if q.front+1 >= len(q.list) {
        q.front = (q.front + 1) % len(q.list)
    } else {
        q.front += 1
    }
    return q.list[q.front], nil
}

//创建队列
func NewDQueue(cap int) *DQueue {

    return &DQueue{
        front: -1,
        rear:  -1,
        list:  make([]interface{}, cap),
    }
}

测试代码

func TestQueue(a *testing.T) {

    //初始化队列，空间为10
    queue := NewDQueue(10)

    for i := 1; i < 100; i += 2 {

        err := queue.Add(fmt.Sprintf("元素%d", i))
        log.Printf("错误信息：%v------队列：%v", err, queue.list)
        if err != nil {
            break
        }

    }

    //从队列获取元素
    for {
        data, err := queue.Poll()
        log.Printf("%v------%v", data, err)
        if err != nil {
            break
        }
    }

}

测试结果如下

微信图片_20200630155933.png

ps:这个例子着重记录，顺序存储的队列的算法，每次只能入队一个元素，也是非线程（goroutine）安全的,如果要保证线程安全，可以使用sync包的Mutex锁，如果是为了支持goroutine安全又能实现队列的效果，直接使用go原生的 带缓存的 channel 更合适，此处单纯为了复习算法