基础技能树-22 基于数组实现数据结构

2017-11-14 12:18:02来源:cnblogs.com作者:李永京人点击

分享

本节内容

  • 开篇
  • 栈(Stack)
  • 队列(Queue)
  • 缓冲区(Pool)[付费阅读]
  • 链表(Linked List)[付费阅读]

开篇

很显然数组带来很大的好处,直接的好处有几点,第一它是一块完整的连续的内存而且只需要一次性分配,第二数组本身访问效率很高,第三我们可以对数组进行复制,因为数组只有一块内存,我只要把这一块的内存完整复制就可以了,而其他的很多复合结构可能有多块内存组成的,我们想复制的时候并不容易。比如切片还好点只有两块内存,比如像链表可能有很多块内存,我们想复制一个链表的时候我们得遍历一块一块的复制,所以数组先天性的具备了性能上的优势,我们承认数组在操作上的确有很多麻烦,但数组的性能不能忽略。接下来我们做的是能不能用数组实现常用的数据结构。第一我们使用数组带来的性能优势,第二把数组转换为另外的访问方式带来操作上的便利性。把这两者结合起来,因为直接操作数组的很多时候比较麻烦,比如我们插入、删除这些操作不特别方便。所以我们接下来把数组和其他数组结构访问上的便利性结合起来。

栈(Stack)

栈是很典型的先进后出(FILO)数据结构。其实我们在前面接触很多的栈,调用堆栈本身就是一个栈结构,它是一个内存空间,地址从高位到低位分配,首先高位记录一个位置,比如使用BP寄存器保存,另外一个位置用SP寄存器来处理当前栈顶的位置。加一个数据即Push操作SP往上减,弹出一个数据即Pop操作SP往下增。很显然用一个数组加两个字段来模拟SP、BP就可以了。我们怎么样去做呢,用一个最简单的做法就是第一种方式使用一个结构体,指针属性指向一个数组,数组天生就包含了起始位置BP和容量cap,或者这个数组直接内联,然后SP属性记录栈顶的位置就可以实现简单栈的管理。还有个简单的方式使用一个数组,把位置一当作BP寄存器使用,假如我们需要分配四个元素项的栈,那么实际分配就是4+1,把索引0当作BP来用,以后就是操作数组后面的空间。这样的方式与结构体类似,因为结构体本身内存也是连续的,一块是数组,一块是BP,结构体也是这样的数据结构本质上是一回事。当然也可以用数组方式做,只需要有个地方记录一下BP的值就可以了,所以整个的栈结构实现起来非常的简单。

s是一个动态的内存,所以我们用切片的方式去创建,切片看上去和数组是一样的,我们的目的是获得一个动态数组,我们把容量+1,用0来当作BP寄存器来用。首先初始化的时候0指向栈底的位置,然后往里加数据的时候BP往上移,所以BP初始化的时候指向最后一个位置。接下来往里面加数据的时候,读取BP寄存器的值,如果这时候SP指向0的位置的时候栈已经满了,先判断栈是否已经满了,满了的话返回一个错误,如果不满的话直接把数据写进去,同时往里压数据的时候,每压一个数据,BP寄存器往上移一次,表示下次可以往新的地方写。弹出数据的时候,BP寄存器记录的是最后一次可写的位置,可写和可读的数据中间应该差一个,首先加上1调整BP寄存器位置,如果这个位置指向最低的时候表示没有数据了,表示为空,如果有数据就返回,同时调整BP寄存器,因为我们知道弹出数据的时候,SP往下做加法,压数据的时候,SP往上做减法。整个操作很简单也就是4-5行核心代码。

如果不用数组用链表实现队列和栈最简单的,但是链表在内存管理上有很大的缺陷。

package mainimport "errors"type Stack []intvar (    ErrStackFull  = errors.New("stack full")    ErrStackEmpty = errors.New("stack empty"))func NewStack(cap int) Stack {    s := make([]int, cap+1)    s[0] = cap    return s}func (s Stack) Push(v int) error {    i := s[0]    if i == 0 {        return ErrStackFull    }    s[i] = v    s[0] = i - 1    return nil}func (s Stack) Pop() (int, error) {    i := s[0] + 1    if i == cap(s) {        return 0, ErrStackEmpty    }    v := s[i]    s[0] = i    return v, nil}

队列(Queue)

队列是很典型的先进先出(FIFO)数据结构。队列如果是一个数组结构,我们从左往右加数据,实际上有两个属性需要注意的,第一个是写W的位置,第二个是读R的位置。比如我们可以连续写3个格子,写的位置就到位置4,读的位置还是停留在位置1,所以读和写的位置是不一样的。这地方就有个问题,我们怎么维护读和写的位置。比如说写满了以后就不能写了,我们通常会实现一个环状队列,比如写满了,接下来读操作,读到位置3,那么1-2空间就重新可用了,写的位置就会调整到位置1,这就有个麻烦,W可能大于R,W也可能小于R,我们怎么处理这个呢?

记录当前元素数量记录W和R的位置,因为W和R默认都为0,当往里面写的时候数量会递增,当数量等于容量的时候表示满了,假如数据数量是2,在位置2和位置3,W写的时候写在位置4,写满了,这时候数据数据不等于容量,怎么知道W需要回头呢。所以W和R除了要和数据数量比较还需要和容量即最后一个索引号比较。如果等于最大的索引号,W就需要回头。

第一个背景,假设有这样的一个容器,4个格子,我们有个指针一直做加法,那么到一定程度就超出了容器的限制,不管这个指针超出多大,我们对于指针与容量取模操作结果值肯定是在容量范围之内。任何一个数字除以一个固定容量那么余数肯定会在这个范围之类。

第二个背景,队列R和W最大的麻烦是队列有长度限制,因为有长度限制,所以R和W有回头操作,假如长度没有限制无限长,那么W永远大于等于R,W减去R肯定是当前数据长度,这样的话,队列长度无限的,判断逻辑就非常简单。

我们把第一个背景和第二个背景组合到一起,如果变成一个环,假如这个队列是个环状的,假如这个环是无限大小的,那么R到W区域就是有数据的。问题是真实情况我们的队列肯定是有限制的,我们用抽象大小的环来处理R和W的值,第一个用抽象的处理R和W,避免R和W回头操作,第二个在数据读写的时候,去做取模操作,因为取模操作就可以映射到真实的容量具体的位置上面,那么接下来需要判断事就很简单,要么写满了,要么是空的没数据。

package mainimport (    "errors")type RingQueue struct {    data []int    head int    tail int}var (    ErrQueueFull  = errors.New("queue full")    ErrQueueEmpty = errors.New("queue empty"))func NewRingQueue(cap int) *RingQueue {    return &RingQueue{        data: make([]int, cap),    }}func (q *RingQueue) Push(x int) error {    if (cap(q.data) - (q.tail - q.head)) == 0 {        return ErrQueueFull    }    n := q.tail % cap(q.data)    q.data[n] = x    q.tail++    return nil}func (q *RingQueue) Pop() (int, error) {    if q.tail == q.head {        return 0, ErrQueueEmpty    }    n := q.head % cap(q.data)    x := q.data[n]    q.head++    return x, nil}

这是很简单的数据结构,一个数组,一个读一个写,写的位置作为头head,读的位置作为尾tail。头和尾之间的区域就是有数据的区域。往里面写Push的时候,先判断下当前是否有真实的地方有空位,假如无限大小的,tail减去head是有数据的区域,总长度减去有数据的长度就是空位长度,所以cap(data) - (tail - head)就是是否有空位,那么tail和head一直累加和总长度没有关系的,这样的话首先判断是否有空位,如果空位等于零就表示已经满了,直接返回一个错误。如果没有满,把尾部的信息取模操作就是把抽象的环映射到真实的数据结构上面。接下来在真实位置写,然后把抽象环上的tail值累加。读操作其实也是一样的,所以说这地方只有两个概念构成,抽象大小的环处理tail和head的位置,这两个位置只是要判断有数据的长度或者是空位的长度,有数据的长度大于零代表有数据,空位的长度大于零代表有写的位置。对应映射固定长度的队列,有数据队列上肯定有数据的,有空位队列上肯定有空位的。

这样一来我们就不需要处理tail和head前后的问题了,把这个逻辑变得很简单了,有些时候我们需要用抽象的概念去处理复杂的逻辑,就是把复杂的逻辑抽象化。我们借助抽象的概念来处理简单的索引位置。这是一个很典型的环状设计。

package mainimport "fmt"func main() {    s := NewRingQueue(3)    fmt.Println(s.Push(1), s)    fmt.Println(s.Push(2), s)    fmt.Println(s.Push(3), s)    fmt.Println(s.Push(4), s)    fmt.Println(s.Pop())    fmt.Println(s.Pop())    fmt.Println(s.Pop())    fmt.Println(s.Pop())    fmt.Println(s.Push(4), s)    fmt.Println(s.Push(5), s)    fmt.Println(s.Pop())}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台