山东大学：《数据结构》课程教学资源（PPT课件讲稿）第5章 堆栈（STACKS）Restricted version of a linear list

第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. }

52 Derive class and inheritance(派生类和继承) a Class b that is a specialized or restricted version of another class a may be derived(派生) from the class, a is called based class and b the derived cass. B inherits(继承) all of the members- public protected and private of A, and all data members and functions of a are associated with every object of type B. Furthermore a class can be derived from more than one class, e. g. from A, C 山东大学计算机科学与技术学院数据结构第5章堆栈

山东大学计算机科学与技术学院 数据结构 第5章 堆栈 6 5.2 Derive class and inheritance(派生类和继承) ◼ A Class B that is a specialized or restricted version of another class A may be derived (派生）from the class. A is called Based class and B the derived class. B inherits (继承） all of the members –public, protected and private of A, and all data members and functions of A are associated with every object of type B. Furthermore a class can be derived from more than one class, e.g. from A,C

Three ways to inherent Using class header syntax(语法) to specify class B: public A //public Class b inherent all public and protected members of A class B: public A, private C Class b inherent the public and protected members of A but all the public and protected members of C become the private members of B. class B: protected A All public and protected member of a become the protected member of B NOTE: in all model of inheritance, the private members of a remain private to a and are not accessible from members of b 山东大学计算机科学与技术学院数据结构第5章堆栈 7

山东大学计算机科学与技术学院 数据结构 第5章 堆栈 Three ways to inherent ◼ Using class header syntax (语法） to specify class B: public A //public ◼ Class B inherent all public and protected members of A class B: public A, private C ◼ Class B inherent the public and protected members of A, but all the public and protected members of C become the private members of B. class B: protected A ◼ All public and protected member of A become the protected member of B. ◼ NOTE: in all model of inheritance, the private members of A remain private to A and are not accessible from members of B. 7

usage If X is of type B, we can use function F on X by writing X Fo only when f is a public member of either b or a 山东大学计算机科学与技术学院数据结构第5章堆栈

山东大学计算机科学与技术学院 数据结构 第5章 堆栈 usage ◼ If X is of type B, we can use function F on X by writing X.F () only when F is a public member of either B or A. 8

5.3 formula-based representation Since a stack is a linear list with the restriction that additions and deletions take place and the same end If we use formula-based representation top element of stack- elemenet (length-1; and bottom=element[01 The class stack defined in program 5.1 is a derived class of linearlist( Program 3. 1), where the inheritance model is private, it means that the public and protected members of linearlist are accessible bu members of stack, but not by stack instances 山东大学计算机科学与技术学院数据结构第5章堆栈

山东大学计算机科学与技术学院 数据结构 第5章 堆栈 9 5.3 formula-based representation Since a stack is a linear list with the restriction that additions and deletions take place and the same end. If we use formula-based representation, top element of stack= elemenet[length-1]; and bottom=element[0] The class stack defined in Program 5.1 is a derived class of LinearList( Program 3.1), where the inheritance model is private, it means that the public and protected members of LinearList are accessible bu members of Stack, but not by stack instances

1. Program 3.1 template class linearlist{∥公式化描述的线性表 public: LinearList(int MaxListSize 10) LinearListoi delete l element;) bool Isempty o const i return length ==0; y int Lengthy const i return length; y bool Find(int k, T& x) const int Search(const t& x) const LinearList& delete(int k t&X LinearList& insert(int k, const T& x) void Output(ostream& out) const private: int length int Maxsize; T * element. 山东大学计算机科学与技术学院数据结构第5章堆栈

山东大学计算机科学与技术学院 数据结构 第5章 堆栈 10 1. Program 3.1 template class LinearList { //公式化描述的线性表 public: LinearList(int MaxListSize = 10); ~LinearList() { delete [] element; } bool IsEmpty() const { return length == 0; } int Length() const { return length; } bool Find(int k, T& x) const; int Search(const T& x) const; LinearList& Delete(int k, T& x); LinearList& Insert(int k, const T& x); void Output(ostream& out) const; private: int length; int MaxSize; T *element; };