文档介绍：数据结构
Data Structure
张先宜 ********** zxianyi@
1
第3章队列
队列的定义和运算
顺序队列和循环队列
2
队列也是线性表,是操作受限的特殊的线性表。线性表的插入、删除操作是不受限制的;队列的插入操作在表的一端进行,删除操作在表的另一端进行。
但从数据类型角度看,队列是和线性表不相同的两种重要的数据结构。在计算机科学和程序设计中有广范的应用。
3
队列
队列(Queue)也是一种基本的、重要的、应用广泛的数据结构。
队列是按“先进先出”操作方式组织的数据结构。
日常生活中队列操作方式实例:
人类在争用某些稀缺资源时,为体现公平,往往采取排队的解决办法,按“先来先服务”的原则使用这些资源。
春节排队购买火车票;食堂排队买饭等。
计算机中栈的应用实例:
早期Host+Terminal系统,终端争用CPU;
许多类型CPU的内部就构建了取指令队列,加快指令执行速度;
4
计算机中队列的应用实例:
计算机主机向外设传输数据,比如打印机打印文档,当外设速度较慢,来不及处理主机传来的数据时要使用队列对数据进行缓冲;
操作系统中的进程、线程调度等用到队列,Windows操作系统更是大量使用信息队列,利用消息驱动来调度和管理计算机系统,系统运行时构建众多的消息队列,将不同的消息放入不同的消息队列进行管理;
网络应用系统中队列也得到广泛的使用,比如C/S模式系统中,服务器为了处理众多客户端的并发访问,会用队列对客户端的服务请求进行管理;
此外,解决实际问题的应用系统中也会经常使用队列。
5
学****队列结构时,需要掌握哪些方面的内容?
请看下图:
逻辑结构
运算定义
逻辑结构
存储结构
运算实现
算法分析
数据结构的组成
6
队列基本概念
队列(Queue)
是限定只能在一端插入元素,另一端删除元素的线性表,也称作先进先出表。
空队列
没有元素的队列。
a1
a2
…
an-1
an
出队
入队
队头(front)
队尾
(rear)
7
队头(front)
删除元素的一端。
队尾(rear)
插入元素的一端。
入队
插入操作,即队尾插入。
出队
删除操作,即删除队头。
队列的特性
先进先出(FIFO—First In, First Out)
队列也是操作受限的线性表。
8
队列的基本运算
1. 队列的基本运算定义
(1) 初始化:设置队列为空。
(2) 判断队列为空:
若为空,则返回TRUE,否则返回FALSE.
(3) 判断队列为满:
若为满,则返回TRUE,否则返回FALSE.
(4) 取队头元素:取出队头元素。
条件:队列不空。
否则,应能明确给出标识,以便程序的处理。
(5) 入队:将元素入队,即放到队列的尾部。
如果队列满,怎样处理?
(6) 出队:删除当前队头的元素。
如队列空而不能进行,应怎样处理?
9
2. 杜列的运算的C++描述
任何数据结构的描述和实现都包括2个部分:数据(数据元素及其关系)和运算;
C++如何描述队列结构呢?一种方案:将队列的数据和运算封装成C++的类。
成员变量—描述数据
成员函数—描述运算
队列的C++类描述框架:
【思考问题】
不用类其数据结构如何描述呢?
class Queue
{
运算描述部分;
数据描述部分;
};
10