DataStructure - 队列 (Queue)

队列

队列可以说是程序设计中 最常用 的数据结构,也是 并行设计中最重要 的数据结构.

队列也比较好理解,因为时时刻刻发生在我们身边

生活中,比如 排队买票,先排队的,先买到票,卖完票走出队伍 (队列) ,迟来的买票人 ,只能排在队伍后面 ,也即向队列后面实行添加操作.还有很多 比如 停车场

OS中使用队列来实现进程间通信---消息传递,

也使用队列完成作业之间的调度,比如在请求打印服务,如果请求的服务过多,系统会要求它们按时间 或 优先级 存储在一个队列中,根据队列的顺序 一个一个完成打印操作.

程序设计时经常被用来当作临时buffer(缓冲区) , 当程序处理不过来时,会暂时存储在buffer中,等IO(一般都是IO)反应过来时再从buffer中按序取数据.所以队列真是无处不在.

在众多程序语言中,有这样一种数据结构天生具备队列的特性 ,那就是数组, 比如我们使用Python的List来模拟队列一下.

>>> Queue = [] #一个队列(py's List)
>>> Queue.append(1)
>>> Queue.append(2)
>>> Queue.append(3) #依次添加三个元素 1, 2, 3  | 就像排队一样 1 排在最前面
>>> Queue
[1, 2, 3]
>>> Queue.remove(1) #删除元素,类似出队列.
>>> Queue
[2, 3]
>>> Queue.append(4) #增加新元素
>>> Queue
[2, 3, 4]
>>> 

如上面的程序所示，队列的操作非常简单,但是它却如此重要。

队列设计 -- 顺序队列 (链式队列操作和链表操作大体相同. 所以这里主要讲解顺序队列)

队列的基本操作有 入队 ,它在末端会插入一个元素, 还有出队,在开头删除一个元素.所以它和栈一样,对于任意操作,链式队列和顺序队列的时间复杂度都为 常数时间.

顺序队列的的ADT 需要一个存储数据的数组, 还有两个位置索引 front 和 Rear,它们代表队列的两端(Rear代表后一个元素的后继),还要记录下最大存在于队列中的个数size.

来看下实际队列的索引移动过程.

Step 1时 为一个空的队列, 每向队列中插入一个元素, Rear需要往后挪一格, 当删除队列中开头元素时,front需要往后挪一格,! Step 5 时也是个空队列了.

我们来考虑下极限状况, 比如 队列满的时候. 出现如下状况:

所以,队列的判断是否已满 可以使用 Rear % size == front 来判断. 另外根据图示可以看出, 构造一个队列 需要多开辟一个空间. 而且这个空间不存储任何元素.

入队:

template <class T>
void QueueArray<T>::EnQueue(T& elm) {
	 if (front == rear % size) { return ; }
	 Queue[rear] = elm;
	 rear = (rear+1) % size;	
}

出队:

template <class T>
T QueueArray<T>::outQueue() {
	 int old = front;
	 front = (front+1) % size;	/**< front + 1 */
	 
	 return Queue[old];			/**< 返回out的值 */
}

优先级队列(Priority Queue):

所谓优先级队列就是在上文说的普通队列中加入了优先级的概念, 如果一个队列中的元素的优先级都相同,那么就按先来先服务的原则. 但是如果有其中一个元素优先级较高,则被优先服务, 等执行完了 再执行剩下的元素.

在OS中有很多地方使用了优先级队列:

(1). 作业调度

--->多级反馈队列算法 是轮转法 和 优先级算法的综合,核心思想是设计多个队列,分别赋予不同的等级,优先级等级越低则时间片越长. 仅当较高优先级的队列为空时,才调度较低优先级的队列中进行,如果执行的过程中,有新进程进入较高优先级的队列,则抢先执行新的进程,并把被抢先的进程投入原队列末尾.

(2). 页面置换

---> 页面置换算法 也就是传说中的FIFO, LRU, NFU了,也即先进先出, 最近最少使用页面淘汰, 最不经常使用页面淘汰算法.

所谓LRU是 选择离最后一次访问时间离现在时间最长的一页 进行淘汰.设计出发点在于 某一页被访问了,那么它很有可能马上有被访问 如果很长时间都没有使用,那么很可能最近一段时间也不会访问到.

LRU是和时间长度有关,而 NFU是和访问次数有关,也即访问次数越少说明越容易被淘汰.设置给每个页一个计数器,初始化为0 , 每次发生缺某页中断时,则某页的计数器自增 1.

(4). I/O管理

---> I/O调度程序把I/O设备分配给队列中的第一个进程,如果有较高优先级的,那么队列就按优先级从高到低排队.

优先队列的数据结构设计和普通队列一样需要两种操作,一种是入队,还有一种是删除最小,也就是和普通队列一样的出队,不同的是 删除最小的任务是找出,然后再删除优先队列中最小的元素.其它几乎都和普通队列类似.