Chapter 2 Elementary Data Structures Example Spelling checker Look up words in a list of correctly spelled words Add or remove words from the list How to implement Operations needed Insert Find Delete Called ADT Dictionary How to implement Abstract Data Types ADTs An abstract data type ADT is an abstraction of a data structure An ADT specifies Data stored Operations on the data Error conditions associated with operations An ADT is implemented with various concrete data structures Example ADT modeling a simple stock trading system The data stored are buy sell orders The operations supported are order buy stock shares price order sell stock shares price void cancel order Error conditions Buy sell a nonexistent stock Cancel a nonexistent order Chapter 2 1 2 4 Elementary Data Structures Introduction Stacks Queues Lists and Sequences Trees Example Problem Managing Call Frames ADT Implementation The Stack ADT 2 1 1 The Stack ADT stores arbitrary objects Insertions and deletions follow the last in first out scheme Think of a spring loaded plate dispenser Main stack operations push object inserts an element object pop removes and returns the last inserted element Auxiliary stack operations object top returns the last inserted element without removing it integer size returns the number of elements stored boolean isEmpty indicates whether no elements are stored 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 In the Stack ADT operations pop and top cannot be performed if the stack is empty Attempting the execution of pop or top on an empty stack throws an EmptyStackException Applications of Stacks Direct applications Page visited history in a Web browser Undo sequence in a text editor Chain of method calls in the Java Virtual Machine or C runtime environment Indirect applications Auxiliary data structure for algorithms Component of other data structures Method Stack in the JVM main int i 5 The Java Virtual Machine JVM keeps track of the chain of active foo i methods with a stack When a method is called the JVM pushes on the stack a frame containing Local variables and return value Program counter keeping track of the statement being executed When a method ends its frame is popped from the stack and control is passed to the method on top of the stack foo int j int k k j 1 bar k bar int m bar PC 1 m 6 foo PC 3 j 5 k 6 main PC 2 i 5 Array based Stack 2 1 1 A simple way of implementing the Stack ADT uses an array We add elements from left to right A variable t keeps track of the index of the top element size is t 1 S 0 1 2 Algorithm pop if isEmpty then throw EmptyStackException else t t 1 return S t 1 Algorithm push o if t S length 1 then throw FullStackException else t t 1 S t o t Growable Arraybased Stack 1 5 In a push operation when Algorithm push o the array is full instead of if t S length 1 then throwing an exception we A new array of can replace the array with a size larger one for i 0 to t do How large should the new A i S i array be S A incremental strategy increase t t 1 the size by a constant c doubling strategy double the S t o size Comparison of the Strategies We compare the incremental strategy and the doubling strategy by analyzing the total time T n needed to perform a series of n push operations We assume that we start with an empty stack represented by an array of size 1 We call amortized time of a push operation the average time taken by a push over the series of operations i e T n n Analysis of the Incremental Strategy We replace the array k n c times The total time T n of a series of n push operations is proportional to n c 2c 3c 4c kc n c 1 2 3 k n ck k 1 2 Since c is a constant T n is O n k2 i e O n2 The amortized time of a push operation is O n Direct Analysis of the Doubling Strategy We replace the array k log2 n geometric series times The total time T n of a series of 2 4 n push operations is proportional 1 1 to n 1 2 4 8 2k n 2k 1 1 2n 1 8 T n is O n The amortized time of a push operation is O 1 Accounting Method Analysis of the Doubling Strategy The accounting method determines the amortized running time with a system of credits and debits We view a computer as a coin operated device requiring 1 cyber dollar for a constant amount of computing We set up a scheme for charging operations This is known as an amortization scheme The scheme must give us always enough money to pay for the actual cost of the operation The total cost of the series of operations is no more than the total amount charged amortized time total charged operations Amortization Scheme for the Doubling Strategy Consider again the k phases where each phase consisting of twice as many pushes as the one before At the end of a phase we must have saved enough to pay for the array growing push of the next phase At the end of phase i we want to have saved i cyber dollars to pay for the array growth for the beginning of the next phase 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 We charge 3 for a push The 2 saved for a regular push are stored in the second half of the array Thus we will have 2 i 2 i cyber dollars saved at then end of phase i Therefore each push runs in O 1 amortized time n Example Problem Managing Homework Grading ADT Implementation Queues Queues 18 The Queue ADT 2 1 2 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 object dequeue removes and returns the element at the front of the queue Auxiliary queue operations object front returns the element at the front without removing it integer size returns the number of elements stored boolean isEmpty indicates whether no elements are stored Exceptions Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException Applications of Queues Direct applications Waiting lines Access to shared resources e g printer Multiprogramming Indirect applications Auxiliary data structure for algorithms Component of other data structures Singly Linked List next A singly linked list is a concrete data structure consisting of a sequence of nodes Each …