数据结构+第3章+栈和队列+实验.ppt

数据结构上机实验 实验二、栈和队列及其应用 实验名称：栈和队列及其应用 实验目的： 掌握栈的LIFO（后进先出）结构特点；掌握队列的FIFO（先进先出）结构特点； 理解栈和队列的相关概念； 掌握栈的初始化、插入、删除、判空及取栈顶元素操作； 掌握队列的插入、删除操作。 实验名称：栈和队列及其应用 实验内容： 1、根据栈LIFO的结构特点实现表达式 “(1+2)*(3+4^2)” 的计算过程； 2、创建两个队列P和Q。P中有元素A、B、C；Q中有元素X、Y、Z。请先完成P、Q元素的入队操作，然后实现P、Q中元素互换。 即：由 P： A、B、C； Q：X、Y、Z； 变成 P： X、Y、Z ； Q： A、B、C ； 栈的特点 概念：栈是限定仅在表尾进行插入或删除操作的线性表。 注意：表尾端称为栈顶，表头端称为栈底。 结构：LIFO（last in first out）后进先出结构。 操作：进栈（ push ）和出栈（ pop ） ； 表示形式：顺序表示、链式表示； 栈的特点 栈的示意图： a n a 1 a 2 · · · 出栈 入栈 栈顶 栈底 （a）栈的示意图 （b）用铁路调度站表示栈 栈的特点 栈的两种表示： a n a 1 a 2 · · · 栈顶 栈底 （a）顺序栈示意图 S data next 栈顶 栈底 ^ （b）链式栈示意图 队列 概念：队列是一种FIFO（先进先出）的线性表。只允许在表的一端进行插入，在另一端删除元素。允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。 队列 队列示意图： a1，a2，a3，…，an 出队列 入队列 对头 对尾 队列 链队列