队列 #
- 队列的概念
- 栈和队列
- 循环队列
队列的概念 #
- 队列是只允许在一端进行插入，在另一端进行删除的特殊线性表，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。这和日常生活中排队的概念是相同的,想想是不是排队的你总是会排在最后，然后从队伍头部离开？
- 队列数据结构的特点：先进先出（First In First Out – FIFO），这点很好理解，既然是队伍自然是先来先走。
- 插入和删除操作通常称为入队（offer）和出队（poll）
如下图所示，就像食堂排队买饭一样，排队总是从尾部进入，打到饭后总是从头部离开，同样队列插入一个数据时在尾端，而删除数据则是在头部，这样所有的数据都是先进先出
栈和队列 #
我们可以看到栈和队列都是线性表，并且操作也类似，初学者容易将两者搞混，这里对两者作比较：
- 栈是插入和删除都只在某一端，而队列则是在一端插入，在另一端删除
- 栈是先入后出，而队列则是先入先出
循环队列 #
对于普通顺序队列，入队时会将队尾的位置赋值，赋值后将队尾的位置后移，但在入队时难免会出现以下情况
队列的空间未利用完，但造成数据元素溢出，所以利用循环队列就不会有这样的顾虑
循环队列可以增加队列存储空间的利用效率
小结 #
- 掌握队列的概念
- 正确认识区分栈和队列
习题 #
- 联系生活中先入先出的例子，考虑它们和队列结构的联系
- 为什么队列尾部没有空间时不申请新的空间而是采用循环队列？
