数据结构03-栈

《数据结构03-栈》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructures安海忠博士中国地质大学（北京）人文经管学院院长教授博士生导师国土资源部资源环境承载力评价重点实验室主任电话：01082323793（办），13810910701电邮：ahz369@163.com教学内容第一章绪论第二章线性表第三章栈和队列第四章串第六章树和二叉树第七章图第九章查找第十章内部排序第三章栈和队列3.1栈栈的定义、实现和应用3.2队列队列的定义、实现和应用3.1栈(stack)栈的定义3.1栈(stack)栈的定义栈(Stack)只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom

2、)后进先出(LIFO)出/退栈进/压栈a0an-1an-2topbottom3.1栈(stack)实例列车调度若进站的4辆列车顺序如上所述,那么是否能够得到4312,3241,1423和1342的出站序列子弹夹后来者居上3.1栈(stack)实例进栈示例3.1栈(stack)实例出栈示例3.1栈(stack)基本运算3.1栈(stack)举例回文游戏：顺读与逆读字符串一样（不含空格）用栈来解决回文游戏：每个同学拿出办法（写出步骤）判断是否是回文，如“madam”3.1栈(stack)举例回文游戏：顺读与逆读字符串一样（不含空格）用栈来解决回文游戏：每个同学拿出办法判断是

3、否是回文，如“madam”第一步？读入字符串第二步？去掉空格第三步？压入栈第四步？原串字符与出栈字符依次比较，若不等，则不是回文；若相等，则是回文madam栈顶3.1栈(stack)栈的存储结构用数组实现栈：顺序栈3.1栈(stack)栈的存储结构用数组实现栈结构定义3.1栈(stack)算法入栈算法出栈算法用数组实现栈：顺序栈3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)栈的存储结构用指针实现栈：链栈链栈的

4、结构类型定义3.1栈(stack)栈的存储结构用指针实现的链栈定义3.1栈(stack)算法入栈算法出栈算法3.1栈(stack)应用入栈算法出栈算法本章小结理解线性表的概念：同一类型的元素组成的有限系列熟悉定义在线性表上的基本运算：查找、插入、删除掌握实现线性表的一般步骤掌握用数组实现线性表的步骤和方法掌握用指针实现线性表的步骤和方法掌握单循环链表的实现方法掌握双向链表的实现方法作业1小娜和小丽喜欢游戏，准备开始一个新游戏。在一条直线上放置了n个巧克力棒，小娜从左到右吃，小丽从右到左吃。两个人同时开始吃，且吃的速度是一样的。当玩家吃饭一根巧克力棒后，立即吃下一根。一根巧

5、克力棒只能给一个人吃，当两个人要开始同时吃同一根的时候，小丽会让给小娜吃。现有n根巧克力棒，从左到右给出巧克力棒的长度，请给出算法计算出每个人吃的根数。输入第一行包括一个正整数N(1<=N<=500000)，表示巧克力棒数。接下来一行有n个整数，t1,t2,…,tn(1<=ti<=100),表示从左到右的每个巧克力棒的长度实验任务数据输入输出两个数，小娜和小丽各自吃掉的巧克力棒数数据输出作业2：有序链表的插入