程序设计综合实践-栈和队列_第1页
程序设计综合实践-栈和队列_第2页
程序设计综合实践-栈和队列_第3页
程序设计综合实践-栈和队列_第4页
程序设计综合实践-栈和队列_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

五、栈和队列5.1栈和队列的概念栈(stack)和队列(queue)是两种重要的数据结构，应用广泛。例如，编译程序中的表达式计算，函数调用时的参数传递和返回等都是基于栈来实现的；程序设计中需要先到先处理的信息采用队列管理。栈和队列都是操作受限的特殊线性表。栈是后进先出（LastInFirstOut）的线性表，简称LIFO表，队列是先进先出（FirstInFirstOut）的线性表，简称FIFO表。

1栈主要支持入栈、出栈、取栈顶元素、判空等操作。栈具有最后保存最先输出特性。2图1.6栈示意图队列主要支持入队列、出队列、取队首元素、判空等操作。队列具有最先保存最先输出特性。

3图1.7队列示意图栈的抽象数据类型定义：ADTStack{

基本操作：创建空栈Create()；//创建一个空栈销毁栈Destroy(S)；//销毁一个栈S，不再使用拷贝栈Copy(S)；//根据已有栈S，复制一个新栈，内容相同判空IsEmpty(S)；//判断栈S是否为空栈，若是则返回TRUE，否则返回FALSE获取非空栈栈顶元素GetTop(S)；//返回非空栈S栈顶数据元素非空栈栈顶元素出栈Pop(S)；//非空栈S栈顶数据元素出栈，栈内元素少一个元素入栈Push(S,e)；//元素e入栈S，入栈后位于栈顶}4队列的抽象数据类型定义：ADTQueue{

基本操作：

创建空队列Create()；//创建一个空队列销毁队列Destroy(Q);//销毁一个队列Q，不再使用拷贝队列Copy(Q);//根据已有队列Q，复制一个新队列，内容相同判空IsEmpty(Q);//判断队列Q是否为空队列，返回TRUE或FALSE求长度Length(Q);//返回队列Q中数据元素的个数获取非空队列队首元素GetTop(Q);//返回非空队列Q队首数据元素非空队列队首元素出栈Pop(Q);//非空队列队首数据元素出队列Q，队列内元素少一个元素入队列Push(Q,e);//元素e入队列Q，入队列后位于队尾}55.2栈和队列的实现思路栈和队列是操作受限的特殊线性表，因此，线性表的顺序存储结构和链式存储结构同样适用于栈和队列，只要根据栈和队列的特点稍加变化即可。6图1.8栈的顺序存储示意图7图1.9栈的链式存储示意图8图1.10队列的链式存储示意图9图1.11循环队列示意图主要的入栈、出栈、入队列、出队列操作的时间复杂度均是O(1)。根据前面的知识和程序设计基础，不难实现栈和队列的各项基本操作。C++标准模板库（STL）提供了类和队列的类模板。循环队列的入队列操作算法描述如下：//将元素x入pQueue所指队列，成功返回1，失败返回0boolEnQueue(structSeqQueue*pQueue,DataElemx){if((pQueue->iRear+1)%MaxSIZE==pQueue->iFront)return0;//下一位置已是队首位置，队满pQueue->iDatasA[pQueue->iRear]

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论