数据结构之线性表-顺序存储结构的队列-学习笔记-37

引入

我们之前说,队列我们一般使用的是链式存储结构,而不是顺序存储结构。我们今天就看看如何构造队列的顺序存储结构,然后看看顺序存储结构给队列带来了哪些问题。

想一想

我们假设,有一个队列

  • 有 n 个元素
  • 那么顺序存储结构就需要大于 n 的存储单元
  • 数组下标 0 是头部,n 个元素存储在数组的前 n 个存储单元中。


(图片来自于鱼 C 工作室)

入队

  • 0 号下标是队头
  • 然后数据不断进来,不断移动队尾指针。
  • 只需要将队尾指针+1即可
  • 时间复杂度为 O ( 1 )

出队

  • 因为0号下标是队头
  • 0号到元素出去之后,后面所有的元素都要向前移动一位
  • 就像是排队,第一个人搞定离开,后面的人依次向前走一步
  • 这时候,时间复杂度度就是 O ( n ) 了
  • 出队的效率就大打折扣!

因为出队效率太慢,我们就想

  • 不去限制队头一定是 0 号下标
  • 我们让队头指针也动起来
  • 即0号的元素出去之后,队头指针移动到1号下标
  • 循环往复,这样,出队就不用所有人都移动了
  • 就好像排队,排在第一位的人搞定了,柜台向前移动,到第二个人面前

但是…上面这种情况会遇到这样的问题…

  • 如果就像上面的,只有 5 个元素,下标只到 4
  • 释放了前两个元素,那如果队列满了之后,再插入就会出错

eUdIhtZSQzqtCOAXRlPJ5Q_thumb_4523

所以,因为要解决上面的这种数据输入溢出的问题

  • 如果后面满了,那就把尾指针从头开始,也就是收尾相连
  • 队头和队尾的指针随着输入和输出不断移动

这样的话

  • 一开始 front 和 rear 都指向同一个结点
  • front 始终指向第一个队列中的结点
  • rear 始终指向当前可插入的结点

当然,我们这里想的比较多,如果都清楚的话,就可以开始初始化一个循环队列了。

定义一个循环队列

1
2
3
4
5
struct Queue{
int *base; // 也可以直接使用数组,我们这里用的是基地址
int front; //用于存储头部
int rear; //用于存储尾部
};

定义队列比较简单

  • 一个用于存储数据
  • 两个灵活多变的头部和尾部

初始化一个循环队列

我们将刚才定义的循环队列结构体初始化

1
2
3
4
5
6
7
8
#define MAXSIZE 100
#define LEN sizeof(struct Queue)
void initqueue(struct Queue *q){
//先动态生成存储单元,给 base
q->base=(int *)malloc(MAXSIZE * LEN);
//然后让指针归位到 0
q->front=q->rear=0;
}

大概思路就是

  • 因为顺序存储结构的队列是固定大小的,先动态生成固定大小的内存空间
  • 然后让头指针和尾指针都归位到 0

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!