西安建筑科技大学：《数据结构与算法》课程教学资源（PPT电子教案）第二部分 栈、队列、递归方法_栈 Chapter 2 INTRODUCTION TO STACKS（英文）

Chapter 2 INTRODUCTION TO STACKS [1. Stack Specifications 2. Implementation of Stacks L 3. Application: A Desk Calculator 4.Application: Bracket Matching 5. Abstract Data Types and Their Implementations I6. Pointers and Pitfalls

Chapter 2 INTRODUCTION TO STACKS 1. Stack Specifications 2. Implementation of Stacks 3. Application: A Desk Calculator 4. Application: Bracket Matching 5. Abstract Data Types and Their Implementations 6. Pointers and Pitfalls

2.1 Introduction Specifications A stack is a data structure in which all insertions and 3 deletions of entries are made at one end, called the top of the stack. The last entry which is Top inserted is the first one that will 2 be removed 3 Characteristic. Last In first out

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. 2.1 Introduction Specifications 2 3 4 1 4 3 Top 4 3 3 Characteristic: Last In First Out

Standard Template Library (stl) o The standard template library abbreviated STL)in C++ contains much useful information many functions, and many classes. o The stl provides convenient implementations for many common data structures, including almost all the data structures we shall study in this book

Standard Template Library (STL) • 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 and then we can dene initially empty stack objects and apply methods called push, pop, top and empty. o In C++, a template construction allows us to create data structures whose entries have different types. Example: stack numbers and stack numbers

• We can include the STL stack implementation into our programs with the directive #include and then we can dene 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 numbers and stack numbers

o The stl provides several implementations of various data structures such as stacks o 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. o A second, optional template parameter selects the implementation

• 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 # nclude≤ iostream .h> #include using namespace std void main( / Pre: The user supplies an integer n and n decimal numbers Post: The numbers are printed in reverse order. Uses: the stl class stack and its methods

First Example: Reversing a List #include #include using namespace std; void main( ) /* Pre: The user supplies an integer n and n decimal numbers. Post: The numbers are printed in reverse order. Uses: The STL class stack and its methods */

I int n; double item stack numbers. cout n; for(int i=0; i>nem. numbers. pus tem); 1 cout<<endk<<eIN while(!numbers. emp I cout<<numbers. top()num .pop(; b cout<<end; an element in top of stack is pop off

{ int n; double item; stack numbers; cout> n; for(int i=0; i>item; numbers.push(item); } cout<<endl<<endl; while(!numbers.empty( )) { cout<<numbers.top( )<<" "; numbers.pop( ); } cout<<endl; } declares and initializes a stack of numbers input an integer of push stack input an element push stack output an element in top of stack an element in top of stack is pop off

2.2 Implementation of Stacks Constructor 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

Constructor 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. 2.2 Implementation of Stacks Stack :: Stack( ); Pre: None. Post: The Stack exists and is initialized to be empty

Entry Types, Generics 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 i 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

Entry Types, Generics 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++ templatesfor greater generality

Error Processing 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 Later, we shall use several further values of an error code

Error Processing 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 Later, we shall use several further values of an Error code