数据结构（三）培训演示课件.ppt

数据结构（三） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 内容提要 栈 队列 栈和队列是两种特殊的线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。 栈和队列广泛地应用在各种软件系统中，是程序设计中必须掌握的两种基本数据结构。 什么是栈？ 若限定仅在线性表的一端进行插入和删除操作，这样的线性表称为栈。 能够进行插入和删除操作的一端称为栈顶。另一端则相应称为栈底。 位于栈顶的元素称为栈顶元素，位于栈底的元素称为栈底元素。 不含任何元素的栈称为空栈。 栈的特点是后进先出。(Last In First Out: LIFO) 上溢和下溢 和栈有关的操作 和栈有关的操作： 构造一个不含任何元素的空栈 判断栈是否为空栈 判断栈是否满 返回栈中的元素个数 清空栈 向栈顶压入(添加)一个元素 从栈顶弹出(删除)一个元素 读取栈顶元素 栈作为抽象数据类型 template typename stack_entryclass Stack {public: enum error_code { success, overflow, underflow};protected: ...public: //操作 Stack(); Stack(const Stack copy); ~Stack(); bool empty() const; bool full() const; int size(); void clear();  error_code push(const stack_entry item); error_code pop(); error_code top(stack_entry item) const;}; 栈操作 Stackstack_entry::Stack();// PRECONDITION:// POSTCONDITION: 建立了一个空栈 error_code Stacksack_entry::push(const stack_entry item);// PRECONDITION: 栈未满// POSTCONDITION: 元素item被加入到栈的顶部// REMARKS: 若栈未满,元素item被加入到栈的顶部,若栈已满,返回overflow error_code① Stackstack_entry::pop();// PRECONDITION: 栈非空// POSTCONDITION: 栈顶部的元素被删除// REMARKS: 若栈非空,栈顶元素被删除,若栈是空栈,返回错误代码underflow ① 在实际实现时，error_code 应写作 Stackstack_entry::error_code 栈操作 bool Stackstack_entry::empty() const;// PRECONDITION: // POSTCONDITION: 栈的状态未发生变化// REMARKS: 若栈是空栈,返回true,若栈不是空栈,返回false error_code Stackstack_entry::top(stack_entry item) const;// PRECONDITION: 栈非空// POSTCONDITION: 栈的状态未发生变化// REMARKS: 若栈非空,栈顶元素被读入item中,若栈是空栈,返回错误// 代码underflow 栈结构的使用 int main() { Stackint intStack; //创建一个元素类型是整数的空栈 int n,item; cout “Type in an integer n followed by n numbers” endl; cin n; for (int i=0; in; i++ ) { cin item; intStack.push(item); //将整数item压入栈中 } cout endl; while ( !intStack.empty() ) { //判断栈是否空栈 intStack.top(item); //读取位于栈顶的整数 cout item “ “;  intStack.pop(); //将栈顶的整数弹出 }  cout endl;} 栈的实现 —顺序存储 和线性表类似，栈也有两种存储结构：(1) 顺序存储 (2) 链式存储。 顺序存储：用一组连续的存储单元依次存放自栈底到栈顶的数据元素。 栈的实现 —顺序