数据结构队列Queue

《数据结构队列Queue》由会员分享，可在线阅读，更多相关《数据结构队列Queue（17页珍藏版）》请在装配图网上搜索。

1、Joey.zhuQueue主要内容主要内容数据结构的概念数据结构的概念队列的定义及应用队列的定义及应用队列的基本操作队列的基本操作链队列和循环队列实现链队列和循环队列实现迷宫游戏迷宫游戏inet_itoa引发的思考引发的思考数据结构的概念数据结构的概念数据结构（数据结构（Data Structure）是数据的组织方式。程序中用到）是数据的组织方式。程序中用到的数据都不是孤立的，而是有相互联系的，根据访问数据的需的数据都不是孤立的，而是有相互联系的，根据访问数据的需求不同，同样的数据可以有多种不同的组织方式。求不同，同样的数据可以有多种不同的组织方式。数据的组织方式包含了数据的组织方式包含了存储

2、方式存储方式和和访问方式访问方式这两层意思，二者这两层意思，二者是紧密联系的。是紧密联系的。例如，数组的各元素是一个挨一个存储的，并且每个元素的大例如，数组的各元素是一个挨一个存储的，并且每个元素的大小相同，因此数组可以提供按下标访问的方式，结构体的各成小相同，因此数组可以提供按下标访问的方式，结构体的各成员也是一个挨一个存储的，但是每个成员的大小不同，所以只员也是一个挨一个存储的，但是每个成员的大小不同，所以只能用能用.运算符加成员名来访问，而不能按下标访问。运算符加成员名来访问，而不能按下标访问。一个问题中数据的存储方式和访问方式就决定了解决问题可以采用什么样的算法，要设计一个算法就要同时

3、设计相应的数据结构来支持这种算法。所以对于面向过程的程序设计：算法算法+数据结构数据结构=程序程序 队列的定义队列的定义队列（队列（Queue）是一种先进先出（）是一种先进先出（FIFO）的线性表。）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。它只允许在表的一端进行插入，而在另一端删除元素。允许插入元素的一端叫队尾（允许插入元素的一端叫队尾（Rear），），允许删除元素的一端叫队头（允许删除元素的一端叫队头（Front）。）。插入元素叫做入队，删除元素叫出队。插入元素叫做入队，删除元素叫出队。双端队列双端队列双端队列双端队列队列的变种队列的变种双端队列是限定插入和删除操作在表的两

4、端进行的线性表。双端队列是限定插入和删除操作在表的两端进行的线性表。受限的双端队列受限的双端队列输出受限输出受限输入受限输入受限队列的应用队列的应用打印机打印机允许多道程序运行的操作系统的作业排队允许多道程序运行的操作系统的作业排队操作系统管理和分配系统资源操作系统管理和分配系统资源多进程下的管道通讯结构多进程下的管道通讯结构操作系统中消息机制操作系统中消息机制队列是一种应用很广泛的数据结构，对于各队列是一种应用很广泛的数据结构，对于各种具有种具有“先进先出先进先出”需要排队处理的问题，需要排队处理的问题，都可以应用队列来解决。都可以应用队列来解决。队列的基本操作队列的基本操作InitQueu

5、e(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(&Q)QueueLength(&Q)GetHead(&Q,&e)EnQueue(&Q,&e)DeQueue(&Q,&e)QueueTraverse(&Q,visit()构造空队列构造空队列销毁队列销毁队列清空队列清空队列检测队列是否为空检测队列是否为空获取队列长度获取队列长度获取队头元素获取队头元素插入元素插入元素删除元素删除元素队列中每个元素调用队列中每个元素调用visit（）（）链队列和循环队列链队列和循环队列数据的存储方式链式存储 链队列顺序存储 顺序队列，循环队列链队列长度可以不断变长，而顺序队

6、列或循环队列链队列长度可以不断变长，而顺序队列或循环队列都有最大长度的限制都有最大长度的限制顺序队列顺序队列循环队列循环队列判断队列空间是空还是满可以有判断队列空间是空还是满可以有3 3种处理方法：种处理方法：1.1.设置个标志位来区别队列空还是满设置个标志位来区别队列空还是满2.2.少用一个元素空间，约定以队列头指针在队列尾指针的下一少用一个元素空间，约定以队列头指针在队列尾指针的下一位置上作为队列满的标志位置上作为队列满的标志3.3.记录队列中元素个数是否到限定的最大值记录队列中元素个数是否到限定的最大值链队列链队列迷宫游戏迷宫游戏现在我们用队列解决一个有意思的问题定义一个二维数组：int

7、 maze55=0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,;它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。inet_itoainet_itoa引发引发的思考的思考函数原型：函数原型：char*inet_ntoa(struct in_addr);功能：讲整型的功能：讲整型的ip转成点分十进制的字符串转成点分十进制的字符串它这字符串存到哪去了？它这字符串存到哪去了？我没有在形参中传地址进去啊，这不是要返回局部变量了吗？我没有在形参中传地址进去啊，这不是要返回局部变量

8、了吗？看代码后发现，原来这个变量是声明成了看代码后发现，原来这个变量是声明成了static类型类型的，也就表示这个函数不可重入的，也就表示这个函数不可重入inet_itoa引发引发的思考的思考Static声明的变量在声明的变量在C语言中有两方面的特征：语言中有两方面的特征：1)、变量会被放在程序的全局存储区中，这样可以、变量会被放在程序的全局存储区中，这样可以在下一次调用的时候还可以保持原来的赋值。这一点是在下一次调用的时候还可以保持原来的赋值。这一点是它与堆栈变量和堆变量的区别。它与堆栈变量和堆变量的区别。2)、变量用、变量用static告知编译器，自己仅仅在变量的作告知编译器，自己仅仅在变

9、量的作用范围内可见。这一点是它与全局变量的区别。用范围内可见。这一点是它与全局变量的区别。编译器如何区分同名的全编译器如何区分同名的全局变量和静态局部变量的局变量和静态局部变量的？#includeint data=10;int main()static data=5;printf(%dn,data);return 0;inet_itoa引发引发的思考的思考在函数内是编译器如何区别同名的全局变量和局部变量的？在函数内是编译器如何区别同名的全局变量和局部变量的？使用使用:可以引用全局变量，可以我编译不过？可以引用全局变量，可以我编译不过？inet_itoa引发引发的思考的思考Thank you17