Stack sampling ppt

stack ppt on data structure and stack applications ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
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;