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

1.队列是什么?

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

2.队列经常出现在我们的生活中

上面就是一个排队吃饭的队列,遵循先进先打饭(先进先出),后到没饭(后进后出)的原则。
那只吃饭最积极的黑狗就是队列的头部(head),最后面那只叼着黑碗的傻狗就是尾部(tail),队列的长度是6.

3.队列具有那些属性和方法呢?

  • 头部指针:存储头部元素的下标,初始化时为0
  • 尾部指针:存储尾部元素的下一个位置的下标,初始化时为0
  • 长度:存储队列的长度
  • 初始化空队列
  • 入队操作enqueue()
  • 出队操作dequeue()
  • 读队头元素peek()
  • 判断队列是否为空isEmpty()

4.我们来实现一下

  1. 初始化一个空的队列
初始化的时候,head和tail都指向0
  1. 入队操作
    当队列为空的时候,head指向第一个队列元素的下标(不是data里面的null,而是它的下一个元素),tail指向第一个队列元素的下一个位置的下标。
    当队列不为空的时候,head不变,tail往后移动一位。
    代码如下:
我们创建一个新的队列,并添加三个元素

下面是打印出来的结果:队列长度为3,head为1,tail为4

  1. 出队操作
    如果队列长度为0,直接返回;如果队列长度为1,head和tail重置为0;队列长度大于1的时候,head指针往后移,即加一。tail指针不变。最后返回出队的那只狗。
    我们来实现一下:

我们在之前的队列基础上进行出队操作:

下面是打印的结果:

可以看见,早排队的狗儿有饭吃。‘聪明的狗’出队了,head加1,tail不变
我们再执行两次 dequeue()操作

队列为空了

  1. 其它操作
    还有一些其它方法比如isEmpty(),读者感兴趣可以自己试试。
    good night!
评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复