1QueuesWhat 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 ifempty– 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– front2Array 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 elementof 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= 03Algorithms• 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–
View Full Document
Unlocking...