Data structures and Algorithms: Stacks & Queues includes The Stack ADT (Applications of Stacks, Array-based implementation, List-based stack, Applications); The Queue ADT(implementation with a circular array, List-based queue, Round Robin schedulers). | Stacks & Queues Data structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline and Reading • The Stack ADT (§) • • • • Applications of Stacks (§) Array-based implementation (§) List-based stack (§) Applications (§) • The Queue ADT (§) • Implementation with a circular array (§) • List-based queue (§) • Round Robin schedulers (§) Stacks & Queues 2 Stacks Stacks & Queues 3 The Stack ADT Stack ADT stores arbitrary objects Insertions and deletions follow last-in first-out (LIFO) scheme Main stack operations: push(object): inserts an element pop(): removes and returns the last inserted element Auxiliary stack operations: top(): returns the last inserted element without removing it size(): returns the number of elements stored isEmpty(): returns a Boolean value indicating whether no elements are stored Stacks & Queues 4 Stack Example Operation • • • • • • • • • • • • output stack push(8) - (8) push(3) - (3, 8) pop() 3 (8) push(2) - (2, 8) push(5) - (5, 2, 8) top() 5 (5, 2, 8) pop() 5 (2, 8) pop() 2 (8) pop() 8 () pop() "error" () push(9) - (9) push(1) - (1, 9) Stacks & .
