当前课程知识点：数据结构（Data Structures） > 2. List > 2.11 Queue > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
在前面我们已经学习了
栈这种特殊的列表结构
下面我们将继续学习另外一种特殊的列表
队列Queue
那么队列在我们日常生活中
是非常常见的
当我们去排队去做某件事情的时候
就自然而然地形成了一条队列
比如我们排队去买火车票
排在队头的人
将会优先接受这个服务
并且优先离开队列
而后面到来的人
就只能排在队列的末端
而不能够随意地插入到中间的位置
这种常见的结构蕴含着先到先服务
先服务先离开的公平性原则
也就是所谓的FIFO性质
First In Firt Out
最先到来的最先离开
那么对这种常见的队列结构
又应当如何去定义
并且去实现它呢
严格意义上来说
队列它也是一种特殊的列表
它的特殊性体现在
数据的插入和删除的过程
那么在队列中插入数据
是在队列的一端来进行的
而删除则是在队列的另外一端
就像我们前面看到的
生活中的队列例子一样
队列它具有FIFO性质
也就是先进先出的性质
在队列中有一些常见的术语
我们需要了解一下
一个是在队列中插入数据的过程
我们通常称为叫入队
也就是enqueue
而在队列中删除数据的过程
我们叫出队
也叫dequeue
在队列中删除元素的一端
我们称为叫队头
而插入元素的一端我们称为叫队尾
下面我们来看一下队列这个数据结构的
ADT描述
我们可以用一个C++抽象类Queue
来去定义队列的ADT
在这个抽象类中
我们定义了一些常见的操作
首先最常见的是入队操作enqueue
这个函数会把参数e加入到队列中去
和enqueue相对应的是dequeue操作
它将会从队头取出一个元素
并且把它的值记录在引用参数e中
frontValue函数
是读取队头元素的值
然后记录在e中
这个函数和dequeue不同
它不会对这个队列造成任何的改变
最后是length函数
返回队列的长度
clear函数清空队列
下面我们来看一下如何去实现队列
既然队列是一种特殊的列表
那么和列表的实现是相类似的
我们也可以用数组或者是链表来去实现它
这里我们将重点讲一下
比较常见的链表的实现方式
基于链表的实现方式其实非常简单
我们只需要去定义一条链表
然后约定这个链表的一端作为队头
而另外一端作为队尾
为了方便在队头的地方删除元素
我们通常定义链表的第一个元素作为队头
而定义链表的最后一个元素作为队尾
当我们对这个队列
执行dequeue操作的时候
我们只需要取出head
也就是队头它所指向的这个元素就可以了
然后我们去修改head指针
让它指向head后面这个结点
当我们对队列执行enqueue操作的时候
我们就可以去创建一个新的结点
用来去存放入队的元素
然后让原来队尾结点的next指针
去指向这个新结点就可以了
最后别忘了要去修改tail指针
让它去指向新插入的结点
具体的实现我们在这里
就不再去详细地叙述了
大家可以去参考前面的链表的实现
然后在链表的基础上做一些简单的修改
就可以满足这个要求
队列它有着非常广泛的应用
下面我们来看一些具体的例子
比如我们的计算机和外围设备
在一起工作的时候
往往计算机输出的速度
要远远大于外围设备
它所能处理数据的速度
那么当计算机产生的数据
来不及处理的时候
我们可以把这些数据
先放入到一个缓冲区中
而外围设备将从缓冲区里面
去读取需要处理的数据
这里的缓冲区它其实就是一种队列结构
因为先进入缓冲区的数据
将会被优先取出来
又比如在操作系统中
所广泛采用的消息队列
消息队列可以使得不同的软件组件
异步地进行协同工作
比如在图里面
这个B组件要去驱动A组件工作
那么B可以产生相应的调用消息
然后把这个消息放入到消息队列里面去
然后接下来它就可以继续去做其他事情
而无需等待A的确认返回
那么A组件
则不断地从队列里面去取出消息
并且进行相应的处理
那么A和B
它就以一种异步工作的方式在一起工作了
具有比较高的效率
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
