栈和队列

从数据结构看,栈和队列也是线性表,他们是操作受限的线性表。从数据类型来看,它们是和线性表大不相同的两类重要的抽象数据类型。

是限定在表尾进行插入或删除操作的线性表。它是后进先出的线性表。

栈顶:表尾。
栈底:表头。
空栈:不含元素的空表。

队列

队列时一种先进先出的线性表,它只允许在表的一端进行插入元素,在另一端删除元素。

队尾:允许插入的一端。
队头:允许删除的一端。

假溢出

当元素被插入到数组中下标最大的位置上之后,队列的空间就用尽了,尽管此时数组的低端还有空闲空间,这种现象叫做假溢出。

解决:1)将队列元素向前平移。2)使用循环队列。

循环队列

循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。

  1. 初始化队列时,令front = rear = 0
  2. 每当插入新元素时,尾指针加1
  3. 每当删除列头元素时,头指针加1

判断满:

  1. 设一个标志位以区别队列是否空还是满
  2. 少用一个元素控件,约定以“队列头指针在队列尾指针的下一位置上”
Last Updated: 9/25/2019, 10:43:46 PM