This chapter provides knowledge of queues. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Queues 3/16/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Queues © 2014 Goodrich, Tamassia, Goldwasser Queues 1 The Queue ADT q q q q The Queue ADT stores arbitrary q 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: n n enqueue(object): inserts an element at the end of the q queue object dequeue(): removes and returns the element at the front of the queue © 2014 Goodrich, Tamassia, Goldwasser Queues Auxiliary queue operations: n n n object first(): 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 Boundary cases: n Attempting the execution of dequeue or first on an empty queue returns null 2 1 Queues 3/16/14 Example Operation enqueue(5) enqueue(3) dequeue() enqueue(7) dequeue() first() dequeue() dequeue() isEmpty() enqueue(9) enqueue(7) size() enqueue(3) enqueue(5) dequeue() © 2014 Goodrich, Tamassia, Goldwasser – – 5 – 3 7 7 null true – – 2 – – 9 Output Q (5) (5, 3) (3) (3, 7) (7) (7) () () () (9) (9, 7) (9, 7) (9, 7, 3) (9, 7, 3, 5) (7, 3, 5) Queues 3 Applications of Queues q Direct applications Waiting lists, bureaucracy n Access to shared resources (., printer) n Multiprogramming n q Indirect applications Auxiliary data structure for algorithms n Component of other data structures n © 2014 Goodrich, Tamassia, Goldwasser Queues 4 2 Queues 3/16/14 Array-based Queue q q Use an array of size N in a circular fashion Two variables keep track of the front and size f index of the front element sz number of stored elements q When the queue has fewer than N elements, array location r = (f + sz) mod N is the first .
