数据结构中，队列是如何实现先进先出（FIFO）的？

本文共计2479个文字，预计阅读时间需要10分钟。

简介：队列是一种线性表，只允许在一端进行插入操作，在另一端进行删除操作。队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。入队操作。

简介

队列是是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

 

队列是一种先进先出的线性表，简称FIFO允许插入的以端称为队尾，允许删除的一端被称为队头。

入队

出队

队列的两种存储表示：

• 顺序表示：与顺序栈相似，队列的顺序存储结构会用一组地址连续的存储单元依次存储对猎头到队列尾的元素，还分别有头指针和尾指针指向队列头和队列尾。

  • 顺序结构队列的初始化：①设置队列最大长度；②头尾指针为0；③插入新队尾元素，尾指针加一；④删除头元素时，头指针加一。
  • 队列假溢出：当队列的最大空间为6，而头指针为5，尾指针为6时，将不可再继续插入新的队尾元素，实际上队列的实际可用空间并未沾满，此为“假溢出”现象。
  • 假溢出的解决方案：循环队列，队空条件：头指针=尾指针；队满条件：（尾指针+1）%MAXQSIZE == 头指针。　

• 链式表示：用链表标识的队列简称为链队。

  • 链队的初始化：①构造一个只有头结点的控队，头尾指针相等，头结点的指针域为null。
  • 入队：为新队尾元素分配结点，将新结点插入队尾，修改队尾指针的值。
  • 出队：判断对是否为空，空则出错，否则取出队列的队头元素，修改头指针。