文档介绍：栈和队列
实例引入
栈的相关概念
用数组实现顺序栈及操作
用类实现链式栈及相应操作
队列的相关概述

Contents
用数组实现顺序队列及相关操作

用类实现链队列及相应操作

【内容简介】
本章通过实例引入栈和队列的概念,理解栈的“后进先出”和队列的“先进先出”的特点,掌握栈和队列在顺序存储和链式存储结构的特点以及相应的运算,以及栈和队列的实例应用。
【知识要点】
栈和队列的相关概念;
栈的“后进先出”、队列的“先进先出”的结构特点;
栈在顺序存储结构、链式存储结构下的特点及相应算法实现;
队列在顺序存储结构、链式存储结构下的特点及相应算法实现;
实例应用。
第一节

【学习任务】通过工程实例引入,重点理解栈的“后进先出”和队列的“先进先出”的操作特点。
实例:自古华山一条道。
。自古华山一条道,假设道路只能允许一个人通过,那么,游客在登山游览的过程中,只能顺着石路一个接着一个上山,先登山的游客先到达目的地。这就类似于数据结构中的队列,满足“先进先出”的原则。如果在登山的过程中,由于某种原因,有一部分游客不想上山了,在返回的过程中,必须按照后上山的游客先下山,先上山的游客后下山的原则返回。这类似于数据结构中的栈,满足“后进先出”的原则。
华山道路的一段
第二节

掌握栈的定义及相关概念,熟悉栈的操作顺序及元素进出栈的顺序,了解栈的存储结构。
栈的定义
栈是一种特殊的线性表,其全部操作都被限制在表的固定一端进行,而且构成栈的元素必须是同一数据类型。
例如,对于【】,假设有10名游客组成的一个旅游团,其上山的顺序为游客1、游客2、游客3、……、游客10,由于某种原因,这10位游客不想上山了,其下山顺序为游客10、……、游客3、游客2、游客1,,该过程和数据结构中栈的操作一致,其入栈对应上山顺序,其出栈对应下山顺序,满足“后进先出”的顺序。
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶/top ; 表头(即 a1 端)称为栈底/base
例如: 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作,称为入栈。
从栈顶删除最后一个元素的操作,称为出栈。
an称为栈顶元素
a1称为栈底元素
想一想:要从栈中取出a1,应当如何操作?
强调:插入和删除都只能在表的一端(栈顶)进行!