Question

栈和队列 与 数组的关系

Answer 1

栈和队列都可以用数组来存储。

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

栈和队列可以用数组Q[1…m]来存储，数组的上界m即是所容许的最大容量。在运算中需设两个指针：head，队头指针或栈顶指针，指向实际头元素；tail，队尾指针或栈底指针，指向实际尾元素的下一个位置。

扩展资料：

一般情况下，数组的头尾两个指针的初值设为0，这时无论是栈还是队列都为空，没有元素。此时如果还要执行入队操作，则要发生"上溢"，但实际上数组中还有空位置，所以这种溢出称为"假溢出"。

克服假溢出的方法有两种。一种是将数组中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1。