队列

Nahida大约 2 分钟

定义

队列和栈相反，是一种先进先出表。
队列只允许在表的一端插入，在另一端删除。最早进入队列的元素最早离开。
允许插入的一端是队尾（rear），允许删除的一端是队头（front）。

表示

链式表示（链队列）

单链队列的实现：

删除队头元素的实现：

插入元素的实现：

顺序表示（循环队列）

顺序队列使用一组连续的地址存放队头到队尾的元素，用指针front和rear指示队头和队尾的位置。
和栈不同，当到达存储空间边际时，队列的空间往往还没有占满（甚至可能是空的），此时不应分配更大的空间。巧妙的做法是将队列看作环状的空间，称之为循环队列。
循环队列下front和rear指针的位置关系无法指示队列是否已满，因此可以设标志位来标记，或少使用一块空间，该空间不用于存放元素，约定队列front指针在rear指针的“下一位置”（环状状态下）时代表队列已满。

循环队列的实现：

获取队列的长度：

插入元素：

删除元素：