数据结构 JAVA版 栈和队列.pdf

数据结构（Java语言版） 数据结构（Java语言版） ——第4章 栈和队列 ——第4章 栈和队列 主编:王学军 主编:王学军 人民邮电出版社 人民邮电出版社 【内容简介】 【内容简介】 本章通过实例引入栈和队列的概念，理解栈的“后 本章通过实例引入栈和队列的概念，理解栈的“后 进先出”和队列的“先进先出”的特点，掌握栈和 进先出”和队列的“先进先出”的特点，掌握栈和 队列在顺序存储和链式存储结构的特点以及相应 队列在顺序存储和链式存储结构的特点以及相应 的运算，以及栈和队列的实例应用。 的运算，以及栈和队列的实例应用。 【知识要点】 【知识要点】 栈和队列的相关概念； 栈和队列的相关概念； 栈的“后进先出”、队列的“先进先出”的结构特 栈的“后进先出”、队列的“先进先出”的结构特 点； 点； 栈在顺序存储结构、链式存储结构下的特点及相 栈在顺序存储结构、链式存储结构下的特点及相 应算法实现； 应算法实现； 队列在顺序存储结构、链式存储结构下的特点及 队列在顺序存储结构、链式存储结构下的特点及 相应算法实现； 相应算法实现； 实例应用。 实例应用。 第一节 第一节 1.实例引入 1.实例引入 【学习任务】 通过工程实例引入，重点理解栈 【学习任务】 通过工程实例引入，重点理解栈 的“后进先出”和队列的“先进先出”的操作特点。 的“后进先出”和队列的“先进先出”的操作特点。 实例：自古华山一条道。 实例：自古华山一条道。 图4.1所示为华山上山的一段石路。自古华山一 图4.1所示为华山上山的一段石路。自古华山一 条道，假设道路只能允许一个人通过，那么，游 条道，假设道路只能允许一个人通过，那么，游 客在登山游览的过程中，只能顺着石路一个接着 客在登山游览的过程中，只能顺着石路一个接着 一个上山，先登山的游客先到达目的地。这就类 一个上山，先登山的游客先到达目的地。这就类 似于数据结构中的队列，满足“先进先出”的原则。 似于数据结构中的队列，满足“先进先出”的原则。 如果在登山的过程中，由于某种原因，有一部分 如果在登山的过程中，由于某种原因，有一部分 游客不想上山了，在返回的过程中，必须按照后 游客不想上山了，在返回的过程中，必须按照后 上山的游客先下山，先上山的游客后下山的原则 上山的游客先下山，先上山的游客后下山的原则 返回。这类似于数据结构中的栈，满足“后进先出” 返回。这类似于数据结构中的栈，满足“后进先出” 的原则。 的原则。 自 一 古 条 华 道 山 图4.1 华山道路的一段 第二节 第二节 2.栈的相关概述 2.栈的相关概述 掌握栈的定义及相关概念，熟悉栈的操作顺序及 掌握栈的定义及相关概念，熟悉栈的操作顺序及 元素进出栈的顺序，了解栈的存储结构。 元素进出栈的顺序，了解栈的存储结构。 2.1 栈的定义 2.1 栈的定义 栈是一种特殊的线性表，其全部操作都被限制在 栈是一种特殊的线性表，其全部操作都被限制在 表的固定一端进行，而且构成栈的元素必须是同 表的固定一端进行，而且构成栈的元素必须是同 一数据类型。 一数据类型。 例如，对于 【例4.1】，假设有10名游客组成的 例如，对于 【例4.1】，假设有10名游客组成的 一个旅游团，其上