Đang chuẩn bị liên kết để tải về tài liệu:
Data structures and Algorithms: Stacks & Queues

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 (§5.1.1) • • • • Applications of Stacks (§5.1.5) Array-based implementation (§5.1.2) List-based stack (§5.1.3) Applications (§5.1.5) • The Queue ADT (§5.2.1) • Implementation with a circular array (§5.2.2) • List-based queue (§5.2.3) • Round Robin schedulers (§5.2.4) 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 & .