携手创作，一起生长！这是我参加「日新方案 8 月更文应战」的第23天，点击查看活动详情

栈和行列也是一种线性表，可是相关运算有特殊性，所以是一种受限的线性表。

栈

栈是一种只能在一端进行刺进或删去的线性表，且遵从后进先出的准则。

• 表中答应进行刺进、删去操作的一端为栈顶
• 栈顶的当时位置是动态的，有一个称为栈顶的指针的位置指示器指示
• 表的另一端称为栈底
• 添加元素叫入栈，移除元素叫出栈

特色： 后进先出

栈可以由动态数组和链表来完成，所以有两种栈，次序栈和链式栈

链栈：

• 栈纷歧定是次序存储结构，也可以是链式存储结构
• 选用次序存储的栈称为次序栈，选用链式存储的称为链式栈
• 链式存储结构的栈需求规定一切的操作只能在单链表的表头进行，
• 所以它并没有一般意义上的链表的便于增删的长处
• 链栈的长处是不存在栈满上溢的状况

注意：

• 此处所说的栈是一种线性表，与五大内存区域的栈空间不是一个概念。

行列

行列是一种只能在一端进行刺进，在另一端进行删去的线性表，遵从先进先出准则
刺进的那一段称为队尾，删去的那一端称为队头。注意队头队尾不要反了。

存储结构包含次序存储结构和链式存储结构

特色： 先进先出

次序存储结构

需求运用一个数组和两个整数型变量来完成，运用数组次序存储行列中的一切元素，运用两个整型变量分别存储队首元素和队尾元素的下标位置，分别称为队首指针和队尾指针。

次序行列

• 队尾指针总是指向当时行列中队尾的元素
• 队头指针总是指向行列中队头元素的前一个位置

假溢出问题：

• 进队操作会将队尾指针+1，出队操作会将队头指针+1，
• 而队满的条件是队尾指向最终一个空间地址
• 此刻出队若干元素，队头并没有指向第一个位置，就会造成行列中有空位置，但仍然会得到队满的信息，这便是假溢出

环形行列

环形行列可以处理次序行列的假溢出问题，为了处理假溢出，可以充分运用数组中的存储空间，把数组的前端和后端连接起来，构成一个环形的次序表，便是环形行列。

行列操作：

• 在次序行列的基础上，需求进行取余运算
• 队首指针进1：front = (front+1)%MaxSize
• 队尾指针进1：rear = (rear+1)%MaxSize

队满判别条件：

• 约好进队时少用一个数据元素空间
• (q->rear+1))%MaxSize==q->front

队空判别条件：

• q->rear == q->front

链式存储结构

通过节点构成的单链表来完成，只答应在单链表的表首进行删去操作和再单链表表尾进行刺进操作，叫做链队。

总结

• 行列和栈都属于线性表
• 行列遵从先进先出准则，栈遵从后进先出准则