合肥工业大学数据结构课件第二章 栈.ppt

第二章 栈 第二章 栈（stack） 2.1 栈的定义和运算 2.2 顺序栈 2.3 栈的应用 第二章 栈 栈是软件设计中最基本的数据结构， 这是本课程所介绍的第一种数据结构。 学习栈结构时，需要掌握哪些方面的内容？ 为此，回顾一下上一章所介绍的数据结构的组成部分。 由此可知，对每一种结构的学习的组成部分。 2.1 栈的定义和运算 2.1.1栈的定义 栈是只能在一端插入和删除元素的线性表。 术语：栈顶, 栈底, 入栈（压栈）, 出栈（弹栈） 2.1 栈的定义和运算 2.1.2栈的运算 1.栈的基本运算定义 对栈的基本运算有如下几个： (1)初始化 ：设置栈为空。 (2)判断栈为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断栈为满： 若为满，则返回TRUE，否则返回FALSE. (4)取栈顶元素：取出栈顶元素。 条件：栈不空。 否则，应能明确给出标识，以便程序的处理。 (5)入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？ (6)出栈：删除当前栈顶的元素。 如因为栈空而不能进行，应怎样处理？ 2.1.2 栈的运算 2.栈的运算的C++描述 如何用C++描述栈的内容和运算？ 一种方法是： 将栈的有关数据和运算封装在一起， 以C++的类的形式来封装描述。 封装的数据和运算要便于被有关程序来调用。 因此，栈的C++描述的框架如下所示： Class stack { } 2.1.2 栈的运算 下面讨论栈的运算的C++描述的细节，先给出每一个运算的对应描述： 初始化函数的描述 2.1.2 栈的运算 判断函数的对应 2.1.2 栈的运算 其他几个函数的对应描述 分析： （1）几个运算的条件可能有不成立的情况， 因此，需要给与明确的反映。 （2）设立运算是否正常的类型error_code， 正常时返回success, 否则返回错误类型，如overflow, underflow等。 （3）可以将这几个函数的类型设置为error_code； （4）如果需要返回其他的值，可以作为参数来返回。 2.1.2 栈的运算 2.1.2 栈的运算 (6)出栈的运算功能描述： 如果栈不空，删除当前栈顶的元素，并返回success。 否则，返回underflow。 对应的运算函数为： error_code pop(); 2.1.2 栈的运算 由此得到栈的类stack的函数成员列表如下： class stack{ stack(); // 初始化 Bool empty( ) const; // 判断空 Bool full( ) const; // 判断满 error_code get_top(elementtype x) const; // 取栈顶元素 error_code push(const elementtype x); //入栈 error_code pop(); // 出栈 栈的数据成员 } 问题：上述类的描述是否还需要补充什么？ 2.2 顺序栈 2.2.1 存储结构： 假设有一个足够大的存储空间（数组）data,可用于存储栈的元素。 则可将栈中元素连续地存储到数组的各元素----顺序存储方式。 如下图所示： 其中：为了能随时知道栈中的元素个数，设置了一个计数变量count。 将数组data和count作为类stack的数据成员。 2.2 顺序栈 由此而得到类stack的完整描述。 封装类: class