Question? Leave a message!




Stacks

Stacks
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Stacks Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Stacks 2 Outline 3.2 This topic discusses the concept of a stack: – Description of an Abstract Stack – List applications – Implementation – Example applications • Parsing: XHTML, C++ • Function calls • Reverse-Polish calculators • Robert’s Rules – Standard Template LibraryStacks 3 Abstract Stack 3.2.1 An Abstract Stack (Stack ADT) is an abstract data type which emphasizes specific operations: – Uses a explicit linear ordering – Insertions and removals are performed individually – Inserted objects are pushed onto the stack – The top of the stack is the most recently object pushed onto the stack – When an object is popped from the stack, the current top is erasedStacks 4 Abstract Stack 3.2.1 Also called a last-in–first-out (LIFO) behaviour – Graphically, we may view these operations as follows: There are two exceptions associated with abstract stacks: – It is an undefined operation to call either pop or top on an empty stackStacks 5 Applications 3.2.2 Numerous applications: – Parsing code: • Matching parenthesis • XML (e.g., XHTML) – Tracking function calls – Dealing with undo/redo operations – Reverse-Polish calculators – Assembly language The stack is a very simple data structure – Given any problem, if it is possible to use a stack, this significantly simplifies the solutionStacks 6 Stack: Applications 3.2.2 Problem solving: – Solving one problem may lead to subsequent problems – These problems may result in further problems – As problems are solved, your focus shifts back to the problem which lead to the solved problem Notice that function calls behave similarly: – A function is a collection of code which solves a problem Reference: Donald KnuthStacks 7 Implementations 3.2.3 We will look at two implementations of stacks: The optimal asymptotic run time of any algorithm is Q(1) – The run time of the algorithm is independent of the number of objects being stored in the container – We will always attempt to achieve this lower bound We will look at – Singly linked lists – One-ended arraysStacks 8 Linked-List Implementation 3.2.3.1 Operations at the front of a singly linked list are all Q(1) st th Front/1 Back/n Find Q(1)Q(1) Insert Q(1)Q(1) EraseQ(1)Q(n) The desired behaviour of an Abstract Stack may be reproduced by performing all operations at the frontStacks 9 Single_list Definition 3.2.3.1 The definition of single list class from Project 1 is: template typename Type class Single_list public: Single_list(); Single_list(); int size() const; bool empty() const; Type front() const; Type back() const; Single_nodeType head() const; Single_nodeType tail() const; int count( Type const & ) const; void push_front( Type const & ); void push_back( Type const & ); Type pop_front(); int erase( Type const & ); ;Stacks 10 Stack-as-List Class 3.2.3.1 The stack class using a singly linked list has a single private member variable: template typename Type class Stack private: Single_listType list; public: bool empty() const; Type top() const; void push( Type const & ); Type pop(); ;Stacks 11 Stack-as-List Class 3.2.3.1 A constructor and destructor is not needed – Because list is declared, the compiler will call the constructor of the Single_list class when the Stack is constructed template typename Type class Stack private: Single_listType list; public: bool empty() const; Type top() const; void push( Type const & ); Type pop(); ;Stacks 12 Stack-as-List Class 3.2.3.1 The empty and push functions just call the appropriate functions of the Single_list class template typename Type bool StackType::empty() const return list.empty(); template typename Type void StackType::push( Type const &obj ) list.push_front( obj ); Stacks 13 Stack-as-List Class 3.2.3.1 The top and pop functions, however, must check the boundary case: template typename Type Type StackType::top() const if ( empty() ) throw underflow(); template typename Type return list.front(); Type StackType::pop() if ( empty() ) throw underflow(); return list.pop_front(); Stacks 14 Array Implementation 3.2.3.2 For one-ended arrays, all operations at the back are Q(1) st th Front/1 Back/n Find Q(1)Q(1) Insert Q(n)Q(1) Erase Q(n)Q(1)Stacks 15 Destructor 3.2.3.2 We need to store an array: – In C++, this is done by storing the address of the first entry Type array; We need additional information, including: – The number of objects currently in the stack int stack_size; – The capacity of the array int array_capacity;Stacks 16 Stack-as-Array Class 3.2.3.2 We need to store an array: – In C++, this is done by storing the address of the first entry template typename Type class Stack private: int stack_size; int array_capacity; Type array; public: Stack( int = 10 ); Stack(); bool empty() const; Type top() const; void push( Type const & ); Type pop(); ;Stacks 17 Constructor 3.2.3.2 The class is only storing the address of the array – We must allocate memory for the array and initialize the member variables – The call to new Typearray_capacity makes a request to the operating system for array_capacity objects include algorithm // ... template typename Type StackType::Stack( int n ): stack_size( 0 ), array_capacity( std::max( 1, n ) ), array( new Typearray_capacity ) // Empty constructor Stacks 18 Constructor 3.2.3.2 Warning: in C++, the variables are initialized in the order in which they are defined: template typename Type class Stack private: template typename Type int stack_size; StackType::Stack( int n ): int array_capacity; stack_size( 0 ), Type array; array_capacity( std::max( 1, n ) ), public: array( new Typearray_capacity ) Stack( int = 10 ); Stack(); // Empty constructor bool empty() const; Type top() const; void push( Type const & ); Type pop(); ;Stacks 19 Destructor 3.2.3.2 The call to new in the constructor requested memory from the operating system – The destructor must return that memory to the operating system: template typename Type StackType::Stack() delete array; Stacks 20 Empty 3.2.3.2 The stack is empty if the stack size is zero: template typename Type bool StackType::empty() const return ( stack_size == 0 ); The following is unnecessarily tedious: – The == operator evaluates to either true or false if ( stack_size == 0 ) return true; else return false;
sharer
Presentations
Free