Stacks 2010 Goodrich Tamassia Stacks 1 The Stack ADT The Stack ADT stores arbitrary objects Insertions and deletions follow the last in firstout scheme Think of a springloaded plate dispenser Main stack operations push object inserts an element object pop removes the last inserted element 2010 Goodrich Tamassia Stacks Auxiliary stack operations object top returns the last inserted element without removing it integer size returns the number of elements stored boolean empty indicates whether no elements are stored 2 Exceptions Attempting the execution of an operation of ADT may sometimes cause an error condition called an exception Exceptions are said to be thrown by an operation that cannot be executed 2010 Goodrich Tamassia Stacks In the Stack ADT operations pop and top cannot be performed if the stack is empty Attempting pop or top on an empty stack throws a StackEmpty exception 3 Applications of Stacks Direct applications Page visited history in a Web browser Undo sequence in a text editor Chain of method calls in the C runtime system Indirect applications Auxiliary data structure for algorithms Component of other data structures 2010 Goodrich Tamassia Stacks 4 Array based Stack A simple way of implementing the Stack ADT uses an array We add elements from left to right A variable keeps track of the index of the top element Algorithm size return t 1 Algorithm pop if empty then throw StackEmpty else t t 1 return S t 1 S 0 1 2 2010 Goodrich Tamassia t Stacks 5 Array based Stack cont The array storing the stack elements may Algorithm push o become full if t S size 1 then A push operation will throw StackFull then throw a else StackFull exception Limitation of the arraybased implementation Not intrinsic to the Stack ADT t t 1 S t o S 0 1 2 2010 Goodrich Tamassia t Stacks 6 Performance and Limitations Performance Let n be the number of elements in the stack The space used is O n Each operation runs in time O 1 Limitations The maximum size of the stack must be defined a priori and cannot be changed Trying to push a new element into a full stack causes an implementation specific exception 2010 Goodrich Tamassia Stacks 7 Array based Stack in C template typename E class ArrayStack private E S array holding the stack int cap capacity int t index of top element public constructor given capacity ArrayStack int c S new E c cap c t 1 2010 Goodrich Tamassia void pop if empty throw StackEmpty Pop from empty stack t void push const E e if size cap throw StackFull Push to full stack S t e other methods of Stack interface Stacks 8 Stack as a Linked List 5 1 3 We can implement a stack with a singly linked list The top element is stored at the first node of the list The space used is O n and each operation of the Stack ADT takes O 1 time nodes t elements 2006 Goodrich Tamassia Linked Lists 9 Example use in C ArrayStack int A A push 7 A push 13 cout A top endl A pop A push 9 cout A top endl cout A top endl A pop ArrayStack string B 10 B push Bob B push Alice cout B top endl B pop B push Eve 2010 Goodrich Tamassia indicates top A size 0 A 7 size 1 A 7 13 size 2 A 7 outputs 13 A 7 9 size 2 A 7 9 outputs 9 A 7 outputs 9 B size 0 B Bob size 1 B Bob Alice size 2 B Bob outputs Alice B Bob Eve size 2 Stacks 10 Parentheses Matching Each or must be paired with a matching or correct correct incorrect incorrect incorrect 2010 Goodrich Tamassia Stacks 11 Parentheses Matching Algorithm Algorithm ParenMatch X n Input An array X of n tokens each of which is either a grouping symbol a variable an arithmetic operator or a number Output true if and only if all the grouping symbols in X match Let S be an empty stack for i 0 to n 1 do if X i is an opening grouping symbol then S push X i else if X i is a closing grouping symbol then if S empty then return false nothing to match with if S pop does not match the type of X i then return false wrong type if S empty then return true every symbol matched else return false some symbols were never matched 2010 Goodrich Tamassia Stacks 12 Evaluating Arithmetic Expressions Slide by Matt Stallmann included with permission 14 3 2 7 14 3 2 7 Operator precedence has precedence over Associativity operators of the same precedence group evaluated from left to right Example x y z rather than x y z Idea push each operator on the stack but first pop and perform higher and equal precedence operations 2010 Stallmann Stacks 13 Algorithm for Evaluating Expressions Slide by Matt Stallmann included with permission 2010 Stallmann Stacks 14 Algorithm on an Example Expression Operator has lower precedence than 14 4 3 2 7 4 14 3 4 14 7 2 14 2 3 4 14 2010 Stallmann Slide by Matt Stallmann included with permission 2 3 4 14 6 4 14 2 14 Stacks 5 14 F 15 Queues 2010 Goodrich Tamassia Queues 16 The Queue ADT The Queue ADT stores arbitrary objects Insertions and deletions follow the first in first out scheme Insertions are at the rear of the queue and removals are at the front of the queue Main queue operations enqueue object inserts an element at the end of the queue dequeue removes the element at the front of the queue 2010 Goodrich Tamassia Auxiliary queue operations Queues object front returns the element at the front without removing it integer size returns the number of elements stored boolean empty indicates whether no elements are stored Exceptions Attempting the execution of dequeue or front on an empty queue throws an QueueEmpty 17 Example Operation enqueue 5 enqueue 3 dequeue enqueue 7 dequeue front 7 dequeue dequeue empty true enqueue 9 enqueue 7 size 2 enqueue 3 enqueue 5 dequeue Output 5 7 error 9 7 2010 Goodrich Tamassia Q 5 5 3 3 3 7 7 9 9 7 9 7 3 9 7 3 5 7 3 5 Queues 18 Applications of Queues Direct applications Waiting lists bureaucracy Access to shared resources e g printer Multiprogramming Indirect applications Auxiliary data structure for algorithms Component of other data structures 2010 Goodrich Tamassia Queues 19 Array based Queue Use an array of size N in a circular fashion Three variables keep track of the front and rear f index of the front element r index immediately past the rear element n number of items in the queue normal configuration Q 0 1 2 f r wrapped around configuration Q 0 1 2 2010 Goodrich Tamassia r f Queues 20 Queue Operations Use n to determine size and emptiness Algorithm size return n Algorithm empty return n 0 Q 0 1 2 f 0 1 2 r r Q 2010 Goodrich Tamassia f …
View Full Document
Unlocking...