Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17QueuesWhat is a queue?•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: ObjectExample•enqueue(5)•enqueue(3)•dequeue()•enqueue(7)•dequeue()•front()•dequeue()•dequeue()•isEmpty()•enqueue(9)•enqueue(7)•size()•enqueue(3)•enqueue(5)•dequeue()Queue Interfaceint size();bool isEmpty();Object front() throws QueueEmptyException;void enqueue(Object obj);Object dequeue() throws QueueEmptyException;Underlying Representation•Array versus Linked List–Pros and cons?•Running time?–size–isEmpty–enqueue–dequeue–frontArray Implementation0 1 2 3 4 5 6 … n-15 30 1 2 3 4 5 6 … n-1enqueue(5)enqueue(3)dequeue() ?Array Implementation0 1 2 3 4 5 6 … n-15 30 1 2 3 4 5 6 … n-1enqueue(5)enqueue(3)dequeue() ?30 1 2 3 4 5 6 … n-1Circular Array•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 1 2 3 4 5 6 … n-1f rCircular Array•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?0 1 2 3 4 5 6 … n-1f rCircular Array•Need to be able to wrap around•Modulo – %–increment f using (f+1)%n–increment r using (r+1)%n0 1 2 3 4 5 6 … n-1frCircular Array0 1 2fr0 1 2fr0 1 2fr0 1 2fr0 1 2fenqueueenqueuedequeueenqueuer =(2+1)%3= 0Algorithms•size–return (N-f+r) mod N•isEmpty–return (f == r)•front–if isEmpty then throw QueueEmptyException–return array[f]•dequeue–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)%NDeque•Double-ended queue–insertFirst–insertLast–removeFirst–removeLast–first–last–size–isEmptyExample•insertFirst(3)•insertFirst(5)•first()•removeFirst()•insertLast(7)•last()•removeFirst()•removeLast()Doubly Linked List•Algorithms–insertFirst–removeLastObject3prevnexttrailerObject2prevnextObject1prevnextheaderExercises•Implement a queue using two stacks.•Implement a stack using two
View Full Document
Unlocking...