结构体数组 数据结构学习

队列与栈相同，实现一个队列同样需要顺序表或者链表作为基础，因此一个队列既可以是顺序表也可以是链表。但与栈不同不同的是，队列是一种先进先出的线性表，只允许在一段进行插入操作、而在另一端进行删除操作。结构体数组亦或者说，队列要求所有的数据从一端进入，从另一端离开。在队列中允许插入数据的一段叫做队尾，允许数据离开的一端叫做队头。

生活中场景：

相信我们都经历过电脑死机的现象，在死机时，我们经常会点击鼠标进行操作，当然电脑此时并不会出现任何操作，而过了一会，电脑又自动将刚才鼠标点击的操作进行了一遍。这就是因为在操作系统中，多个程序因为需要通过一个通道输出，而按先后次序排队等待造成的。一群人在排队买票，前面的人买好了离开，后面的人就要全部向前一步，补上空位。这些现象就采用了队列的数据结构。

假设队列是q=(a 1 ,a 2 ,......,a n )，那么a 1 就是队头元素，而a n 是队尾元素。这样我们就可以删除时，总是从a 1 开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

队列操作：

ADT 队列(Queue)
Data
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
        InitQueue(*Q): 初始化操作，建立一个空队列Q。
        DestroyQueue(*Q): 若队列Q存在，则销毁它。
        ClearQueue(*Q): 将队列Q清空。
        QueueEmpty(Q): 若队列Q为空，返回true，否则返回false。
        GetHead(Q, *e): 若队列Q存在且非空，用e返回队列Q的队头元素。
        EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
        DeQueue(*Q, *e): 删除队列Q中队头元素，并用e返回其。
        QueueLength(Q): 返回队列Q的元素个数
endADT

顺序表队列：

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。

队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)。

因此我们可以得出一个结论：队列在出队时，一定会全部移动数据。如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列左图所示，front与rear指针均指向下标为0的位置。然后入队a 1 、a 2 、a 3 、a 4 ，front指针依然指向下标为0位置，而rear指针指向下标为4的位置，如图右图所示。

出队a 1 、a 2 ，则front指针指向下标为2的位置，rear不变，如左图所示，再入队a 5 ，此时front指针不变，rear指针移动到数组之外。如右图所示。

假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69035-1.html