队列(Quence)和栈一样，是一种操作受限制的线性表。它只允许在表的后端(rear)进行插入操作，称为入队；在表的前端(front)进行删除操作，称为出队。所以最早进人队列的元素会最先从队列中删除，故队列又称为先进先出(First In First Out,FIFO)的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

　　其结构描述：建立顺序队列结构，必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front,它指向队头元素；另一个是队尾指针rear，指向下一个入队元素的存储位置。

　　队列的实现方式有如下两种：

　　（１）数组方式：根据数据量定义一个数组，以front指向队首元素，值始终为数组首元素a[0]。入队时，根据队列大小将元素存储到相应位置。出队时，front保持不变，删除队首元素，其余元素依次向前移动，队尾指针rear向前移动，时间复杂度为O(N)。上述实现因为不断移动元素，效率太低。

   （２）链表方式：队列中每个元素为一个节点，节点包含值和指向后一个节点的指针。头指针front指向队首节点，尾指针rear指向队尾节点。入队时，队尾节点的节点指针指向新入队节点，队尾指针再指向新入队节点。出队时，队首节点弹出，front节点指向后一个节点。此实现方式效率较高，且可自由伸展队列长度，但所占空间略大于数组方式，如下图所示。

　　队列的基本操作包括入队操作、出队操作、取长度、判断队列是否为空。

　　例题１：：队列实现与测试。

　　程序代码：

　　运行结果：

　　例题２：两个栈实现一个队列。

　　解题思路：栈是先进后出，队列是先进先出，a、b两个栈中以a栈为入栈，b栈为出栈，通过两个栈之间的数据互导实现队列的先进先出。

　　程序步骤如下：

　　(1)声明a、b两个栈。

　　(2)入队操作：首先判断b栈是否为空，如果为空，直接向a栈压入数据；如果b栈不为空，将b栈中所有元素依次弹回a栈，然后向a栈压入新元素。

　　(3)出队操作：首先判断b栈是否为空，如果不为空，直接从b栈中弹出元素；如果为空，则先将a栈中的数据全部依次弹出，随即顺序压入b栈，然后再从b栈弹出元素。

　　(4)再入队操作：首先判断b栈是否为空，如果不为空，先将b栈中的元素依次弹出，顺序压入a栈，直到b栈为空，然后再将新数据压人a栈。

　　(5)再出队操作：首先判断b栈是否为空，如果不为空，直接从b栈中弹出元素；如果为空，则先将栈中的数据全部依次弹出，随即顺序压人b栈，然后再从b栈弹出元素。

　　两个栈实现一个队列的算法图解分析如下图所示。

　　程序代码：

　　运行结果：

　　思考练习题：能否用两个队列实现一个栈？

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社