title: "队列"
date: 2015-05-10 16:32:49
categories: 数据结构
tags: [data-structure,foundation]
概念
- 特殊的线性表；
-
先进先出，尾进头出，FIFO（First In First Out）；
queue
使用场景
- 需要数据元素一个一个被处理时候使用；‘
- 比如：键盘输入、限时抢购等；
顺序存储
- 满足线性表顺序存储的特性；
- 声明：下文的
maxSize= 数组最大长度 - 队头指针
front指向队头元素的数组下标注; - 队尾指针
rear指向队尾元素的数组下标+1； - 为了有效利用空间，防止
假溢出，有了循环队列； - 循环队列的 rear = rear>maxSize ? 0 : rear+1；
- 有了front/rear指针，解决了顺序存储
出队列要移动所有元素的复杂度； - 判空情况：
front == rear; - 队列满时，数组中要有一个
空闲单元； - 队列满情况判断：
(rear+1)%maxSize = front; (取模 “%”)； - 队列实际长度计算公式：
(rear-front+maxSize)%maxSize；
queue-order
链式存储
- 满足线性表链式存储特性；
- 线性表的单链表，
链队列； - 队头
front指针指向链队列的头结点； - 对尾
rear指针指向终端结点； - 空队列时：front和rear都指向头结点；
- 建议使用链式存储实现队列；
-
头结点的数据域可以存队列的实际长度；
queue-chain
讨论板图
queue
