2008级计算机专业数据结构 内部资料,仅供课堂教学使用 Chapter 2 INTRODUCTION TO STACKs P49 1. Stack Specific ations 4. Application: Bracket Matching 2. Implementation of Stacks 5. Abstract Data Types and Their Implementations 3. Application: A Desk Calculator 2. 1]Stack Specifications P50 A stack is a data structure in which all insertions and deletions of entries are made at one end. called he top of the stack. The last entry which is inserted is the first one that will be removed P 52 Pushing and popping a stack 2.1.3 Standard Temp late Library P 52-53, P.55(2.1.5) The standard template library(abbreviated STL) in C++ contains much useful information, many functions, and many classes The STl provides convenient implementations for many common data structures, including almost all the data structures we shall study in this book e We can include the STl stack implementation into our programs with the directive #include <stack and then we can define initially empty stack objects and apply methods called push, pop, top, and empty e In C++, a template construction allows us to create data structures whose entries have different types Example stack<double numbers and stack<int> numbers The STl provides several implementations of various data structures such as stack The code in a client program should not depend on a particular choice of implementation, but the berformance of the final program may very much depend on the choice of implementation. A second, optional template parameter selects the implementation. First Example: Reversing a List P53 2.2] Implementation of Stacks 2.2. Constructor P57-58 The constructor is a function with the same name as the corresponding class and no return type. It is invoked automatically whenever an object of the class is declared Stack: Stack() P None Post The Stack exists and is initialized to be empty Entry Types, Generics P58 For generality, we use Stack entry for the type of entries in a Stack. A client can specify this type with a definition such as typedef int Stack entry; or typedef char Stack entry The ability to use the same underlying data structure and operations for different entry types is called generics typedef provides simple generics. Starting in Chapter 6, we shall use C++ templates for greater generality Error Processing P58-59 We shall use a single enumerated type called Error code to report errors from all of our programs and functions of an the enumerated type Error code is part of the utility package in Appendix C Stacks use three values overflow. underflow2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 2 INTRODUCTION TO STACKS P.49 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Stack Specific ations 2. Implementation of Stacks 3. Application: A Desk Calculator 4. Application: Bracket Matchin g 5. Abstract Data Types and Their Implementations [2.1] Stack Specifications 2.1.2 P.50 A stack is a data structure in which all insertions and deletions of entries are made at one end, called the top of the stack. The last entry which is inserted is the first one that will be removed. P.52 Pushing and popping a stack 2.1.3 Standard Template Library P.52-53, P.55(2.1.5) ⚫ The standard template library (abbreviated STL) in C++ contains much useful information, many functions, and many classes. ⚫ The STL provides convenient implementations for many common data structures, including almost all the data structures we shall study in this book. ⚫ We can include the STL stack implementation into our programs with the directive #include <stack > and then we can define initially empty stack objects and apply methods called push, pop, top, and empty. ⚫ In C++, a template construction allows us to create data structures whose entries have different types. Example : stack<double > numbers and stack<int > numbers ⚫ The STL provides several implementations of various data structures such as stacks. ⚫ The code in a client program should not depend on a particular choice of implementation, but the performance of the final program may very much depend on the choice of implementation. ⚫ A second, optional template parameter selects the implementation. First Example: Reversing a List P.53 [2.2]Implementation of Stacks 2.2.1 Constructor P.57-58 The constructor is a function with the same name as the corresponding class and no return type. It is invoked automatically whenever an object of the class is declared. Stack :: Stack( ); Pre: None. Post: The Stack exists and is initialized to be empty. Entry Types, Generics P.58 For generality, we use Stack entry for the type of entries in a Stack. A client can specify this type with a definition such as typedef int Stack entry; or typedef char Stack entry; The ability to use the same underlying data structure and operations for different entry types is called generics. typedef provides simple generics. Starting in Chapter 6, we shall use C++ templates for greater generality. Error Processing P.58-59 We shall use a single enumerated type called Error code to report errors from all of our programs and functions. The enumerated type Error code is part of the utility package in Appendix C. Stacks use three values of an Error code: success, overflow, underflow