第5章 堆栈( STACKS) Restricted version of a inear list 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 1 第 5 章 堆栈 (STACKS)— Restricted version of a linear list
Contents 5. 1 The abstract Data Type 5.2 Derived classes and inheritance 派生类和继承 5.3 Formula-Based Representation 栈的公式化描述 5.4 Linked Representation 栈的链表描述 n55 Applications应用 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 2 Contents ◼ 5.1 The Abstract Data Type ◼ 5.2 Derived Classes and Inheritance ◼ 派生类和继承 ◼ 5.3 Formula-Based Representation ◼ 栈的公式化描述 ◼ 5.4 Linked Representation ◼ 栈的链表描述 ◼ 5.5 Applications 应用
5. 1 The abstract data type Definition a stack is a linear list in which insertion(addition and deletion take place at the same end the end is called top. the other end of the list is called the bottom e1re2,e3r…reir…ren-1en bottom top 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 3 5.1 The Abstract data type ◼ Definition A stack is a linear list in which insertion(addition) and deletion take place at the same end, The end is called top. The other end of the list is called the bottom ◼ e1 , e2 , e3 , …, ei , …, en-1 , en ↑ ↑ bottom top
Stack configurations E←top D←top D←top CBA C←top B B B A←- bottom A← bottom ←- bottom A← botton Inserto Delete Delete sTack is a table of LIFO ( Last-In, First-Out) 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 4 Stack configurations D ←top C B A ←bottom E ←top D C B A ←bottom D ←top C B A ←bottom C ←top B A ←bottom ⚫Stack is a table of LIFO (Last-In, First-Out) . Insert() Delete Delete
Stack ADT AbstractDataT ype Stack t instances linear list of elements one end is called bottom the other is the top 操作 Create; create an empty stack IsEmpty ( return true if stack if empty, false otherwise IsFullo; return true if stack is full, false otherwise Top; return the top element of stack Add(x); add element x to the stack Delete(x); delete top element of stack and put it in x 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 5 Stack ADT AbstractDataType Stack { instances linear list of elements; one end is called bottom; the other is the top 操作 Create( )；create an empty stack; IsEmpty( )；return true if stack if empty，false otherwise IsFull( )；return true if stack is full，false otherwise Top( )；return the top element of stack Add(x)；add element x to the stack. Delete(x)；delete top element of stack and put it in x. }