栈和队列也是一种线性表,但是相关运算有特殊性,所以是一种受限的线性表。
栈
栈是一种只能在一端进行插入或删除的线性表,且遵循后进先出的原则。
- 表中允许进行插入、删除操作的一端为栈顶
- 栈顶的当前位置是动态的,有一个称为栈顶的指针的位置指示器指示
- 表的另一端称为栈底
- 添加元素叫入栈,移除元素叫出栈
特点: 后进先出
栈可以由动态数组和链表来实现,所以有两种栈,顺序栈和链式栈
链栈:
- 栈不一定是顺序存储结构,也可以是链式存储结构
- 采用顺序存储的栈称为顺序栈,采用链式存储的称为链式栈
- 链式存储结构的栈需要规定所有的操作只能在单链表的表头进行,
- 所以它并没有一般意义上的链表的便于增删的优点
- 链栈的优点是不存在栈满上溢的情况
注意:
- 此处所说的栈是一种线性表,与五大内存区域的栈空间不是一个概念。
队列
队列是一种只能在一端进行插入,在另一端进行删除的线性表,遵循先进先出原则
插入的那一段称为队尾,删除的那一端称为队头。注意队头队尾不要反了。
存储结构包括顺序存储结构和链式存储结构
特点: 先进先出
顺序存储结构
需要使用一个数组和两个整数型变量来实现,利用数组顺序存储队列中的所有元素,利用两个整型变量分别存储队首元素和队尾元素的下标位置,分别称为队首指针和队尾指针。
顺序队列
- 队尾指针总是指向当前队列中队尾的元素
- 队头指针总是指向队列中队头元素的前一个位置
假溢出问题:
- 进队操作会将队尾指针+1,出队操作会将队头指针+1,
- 而队满的条件是队尾指向最后一个空间地址
- 此时出队若干元素,队头并没有指向第一个位置,就会造成队列中有空位置,但仍然会得到队满的信息,这就是假溢出
环形队列
环形队列可以解决顺序队列的假溢出问题,为了解决假溢出,能够充分使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,就是环形队列。
队列操作:
- 在顺序队列的基础上,需要进行取余运算
- 队首指针进1:front = (front+1)%MaxSize
- 队尾指针进1:rear = (rear+1)%MaxSize
队满判断条件:
- 约定进队时少用一个数据元素空间
- (q->rear+1))%MaxSize==q->front
队空判断条件:
- q->rear == q->front
链式存储结构
通过节点构成的单链表来实现,只允许在单链表的表首进行删除操作和再单链表表尾进行插入操作,叫做链队。
总结
- 队列和栈都属于线性表
- 队列遵循先进先出原则,栈遵循后进先出原则
网友评论