数据结构-队列

队列（Queue）简称为队，它也是一种运算「受限」的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行删除。把进行插入的一端称做队尾（Rear），进行删除的一端称做队首或队头（Front）。向队列中插入新元素称为进队或入队（Enqueue），新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队（Dequeue），元素出队后，其后继元素就成为队首元素。

image-20210108193748216

队列的主要特点是「先进先出」，因为队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表。

顺序队

顺序队是队列的顺序存储结构，把元素按照其进队的顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。

约定：

• q->rear指向队尾元素
• q->front指向队头元素的前一个位置
• 初始化时front = rear = -1

顺序队的四个要素：

• 队空条件：q->front == q->rear
• 队满条件：q->rear == MaxSize - 1
• 进队操作：q->rear++;并将要进队的元素e放在q->rear处
• 出队操作：q->front++;并从q->front处取出要出队元素e

当队列非空时，元素的个数m可用q->rear - q->front计算得到，可见：

• 队满时m= MaxSize​
• 队空时m = 0