数据结构-队列

发布于：2022-07-24 ⋅ 阅读:(162) ⋅ 点赞:(0)

队列的概念及结构

队列也是一种特殊的线性表，其操作受到限制。只允许在队列的一端进行插入数据操作，而在队列的另一端进行删除数据操作。

在队列中，进行插入数据操作的一端叫做队尾，其操作叫做入队列或者进队列；而进行删除数据操作的一端叫做队头或者队首，其操作叫做出队列或者离队列。

如上图所示，n1,n2,n3,n4,n5依次从队尾入队，队头元素是n1，队尾元素是n5；而出队只能从另一端队头出，次序依次为n1,n2,n3,n4,n5。这和我们日常生活中的排队相似，最早排队的也是最早离队的，所以队列的特性可以概括为先进先出（First In First Out，FIFO）。

队列的实现可以选择顺序表与链表，但因为队列是在两端进行操作，如果选择顺序表来实现，在进行出队操作的时候需要挪动数据，效率会比较低。所以队列的实现一般都是选择单链表，在单链表的头部进行出队，单链表的尾部进行入队；为了避免在入队的时候需要找尾结点，我们可以事先保存单链表尾结点的地址来提高效率。

初始化队列，将队列的头指针与尾指针置空，也就是创建一个空队列。

销毁的操作就是先将非出队的元素释放，再将头指针与尾指针置空。

如果入队时，队列为空需要将头指针与尾指针指向第一个元素；而其他情况就是将尾指针的next改为newNode的地址，再将尾指针指向newNode。

当出队时，队列中只剩下一个元素需要先释放最后一个元素，再将头指针与尾指针置空；其他情况就是先保存队头元素下一个元素的地址，先将头指针指向的队头元素释放，然后将头指针改为事先保存好的元素地址。