What is a queue Queues First in first out data structure FIFO New objects are placed at rear Removal restricted to front Examples Queue ADT Operations enqueue o Insert o at rear of queue Input Object Output None dequeue Remove object at front error if empty Input None Output Object removed size Return number of objects in queue Input None Output Integer isEmpty Return a boolean indicating queue empty Input None Output Boolean first Return object at front without removing error if empty Input None Output Object Queue Interface int size Example enqueue 5 enqueue 3 dequeue enqueue 7 dequeue front dequeue dequeue isEmpty enqueue 9 enqueue 7 size enqueue 3 enqueue 5 dequeue Underlying Representation Array versus Linked List Pros and cons bool isEmpty Object front throws QueueEmptyException void enqueue Object obj Object dequeue throws QueueEmptyException Running time size isEmpty enqueue dequeue front 1 Array Implementation enqueue 5 enqueue 3 0 1 5 3 0 1 2 3 4 5 6 Array Implementation n 1 enqueue 5 enqueue 3 2 3 4 5 6 n 1 dequeue 0 1 5 3 0 1 0 1 Circular Array 0 2 3 4 5 6 n 1 2 3 4 5 6 n 1 2 3 4 5 6 n 1 Circular Array r 1 3 3 dequeue f 2 f 4 5 6 n 1 f stores index of cell which stores first element of queue r stores index of next available cell in queue Initially f r 0 How do you add a new element How do you remove an element 0 r 1 3 4 5 6 n 1 How do you add a new element insert at array r increment r How do you remove an element return array f increment f What happens when r n 1 Circular Array r 2 Circular Array f f r 0 1 2 r f 0 1 f 0 1 2 3 4 5 6 Need to be able to wrap around Modulo increment f using f 1 n increment r using r 1 n dequeue n 1 0 f 1 r 2 0 1 2 enqueue r 2 1 3 0 enqueue f 2 r enqueue 0 1 2 2 Algorithms size isEmpty Double ended queue return N f r mod N return f r front if isEmpty then throw QueueEmptyException return array f dequeue Deque if isEmpty then throw QueueEmptyException temp array f f f 1 N return temp enqueue if size N 1 then throw QueueFullException SIZE MUST BE N 1 array r object r r 1 N insertFirst insertLast removeFirst removeLast first last size isEmpty Example insertFirst 3 insertFirst 5 first removeFirst insertLast 7 last removeFirst removeLast Doubly Linked List Object1 header Object2 Object3 prev prev prev next next next trailer Algorithms insertFirst removeLast 3
View Full Document
Unlocking...