DOC PREVIEW
UF COP 3530 - Queues

This preview shows page 1-2-3-20-21-22-41-42-43 out of 43 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

QueuesBus Stop QueueSlide 3Slide 4Slide 5The Interface QueueRevisit Of Stack ApplicationsWire RoutingLee’s Wire RouterSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Derive From ArrayLinearListSlide 18Slide 19Derive From ExtendedChainSlide 21Slide 22Slide 23Custom Linked CodeCustom Array QueueSlide 26Slide 27Slide 28Add An ElementSlide 30Remove An ElementSlide 32Moving rear ClockwiseEmpty That QueueSlide 35Slide 36Slide 37A Full Tank PleaseSlide 39Slide 40Slide 41Ouch!!!!!Slide 43Queues•Linear list.•One end is called front.•Other end is called rear.•Additions are done at the rear only. •Removals are made from the front only.Bus Stop QueueBus Stopfrontrearrear rear rear rearBus Stop QueueBus Stopfrontrearrear rearBus Stop QueueBus StopfrontrearrearBus Stop QueueBus StopfrontrearrearThe Interface Queuepublic interface Queue{ public boolean isEmpty(); public Object getFrontEelement(); public Object getRearEelement(); public void put(Object theObject); public Object remove();}Revisit Of Stack Applications•Applications in which the stack cannot be replaced with a queue.Parentheses matching.Towers of Hanoi.Switchbox routing.Method invocation and return.Try-catch-throw implementation.•Application in which the stack may be replaced with a queue.Rat in a maze.•Results in finding shortest path to exit.Wire RoutingLee’s Wire Routerstart pinend pinLabel all reachable squares 1 unit from start.Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 2 units from start.11Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 3 units from start.1122222Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 4 units from start.11222223333Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 5 units from start.1122222333344444Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 6 units from start.1122222333344444555 555Lee’s Wire Routerstart pinend pinEnd pin reached. Traceback.1122222333344444555 55566666666Lee’s Wire Routerstart pinend pin4End pin reached. Traceback.1122222333344444555 555666666663 521Derive From ArrayLinearListwhen front is left end of list and rear is right end•Queue.isEmpty() => super.isEmpty()–O(1) time•getFrontElement() => get(0)–O(1) time•getRearElement() => get(size() - 1)–O(1) time•put(theObject) => add(size(), theObject)–O(1) time•remove() => remove(0)–O(size) time0 1 2 3 4 5 6a b c d eDerive From ArrayLinearListwhen rear is left end of list and front is right end•Queue.isEmpty() => super.isEmpty()–O(1) time•getFrontElement() => get(size() - 1)–O(1) time•getRearElement() => get(0)–O(1) time•put(theObject) => add(0, theObject)–O(size) time•remove() => remove(size() - 1)–O(1) time0 1 2 3 4 5 6e d c b aDerive From ArrayLinearListto perform each opertion in O(1) time (excluding array doubling), we need a customized array representation.Derive From ExtendedChaina b c d enullfirstNodelastNodefront rear when front is left end of list and rear is right end• Queue.isEmpty() => super.isEmpty()– O(1) time• getFrontElement() => get(0)– O(1) timeDerive From ExtendedChaina b c d enullfirstNodelastNodefront rear• getRearElement() => getLast() … new method– O(1) time• put(theObject) => append(theObject)– O(1) time• remove() => remove(0)– O(1) timeDerive From ExtendedChaine d c b anullfirstNodelastNoderear front when front is right end of list and rear is left end• Queue.isEmpty() => super.isEmpty()– O(1) time• getFrontElement() => getLast()– O(1) timeDerive From ExtendedChaina b c d enullfirstNodelastNoderear front• getRearElement() => get(0)– O(1) time• put(theObject) => add(0, theObject)– O(1) time• remove() => remove(size-1)– O(size) timeCustom Linked Code•Develop a linked class for Queue from scratch to get better preformance than obtainable by deriving from ExtendedChain.Custom Array Queue•Use a 1D array queue.queue[]•Circular view of array.[0][1][2] [3][4][5]Custom Array Queue•Possible configuration with 3 elements.[0][1][2] [3][4][5]A BCCustom Array Queue•Another possible configuration with 3 elements.[0][1][2] [3][4][5]ABCCustom Array Queue•Use integer variables front and rear.–front is one position counterclockwise from first element–rear gives position of last element[0][1][2] [3][4][5]A BCfrontrear[0][1][2] [3][4][5]ABCfront rearAdd An Element[0][1][2] [3][4][5]A BCfrontrear•Move rear one clockwise.Add An Element•Move rear one clockwise.[0][1][2] [3][4][5]A BCfrontrear•Then put into queue[rear].DRemove An Element[0][1][2] [3][4][5]A BCfrontrear•Move front one clockwise.Remove An Element[0][1][2] [3][4][5]A BCfrontrear•Move front one clockwise.•Then extract from queue[front].Moving rear Clockwise[0][1][2] [3][4][5]A BCfrontrear•rear++; if (rear = = queue.length) rear = 0;•rear = (rear + 1) % queue.length;Empty That Queue[0][1][2] [3][4][5]ABCfront rearEmpty That Queue[0][1][2] [3][4][5]BCfront rearEmpty That Queue[0][1][2] [3][4][5]Cfront rearEmpty That Queue•When a series of removes causes the queue to become empty, front = rear.•When a queue is constructed, it is empty.•So initialize front = rear = 0.[0][1][2] [3][4][5]front rearA Full Tank Please[0][1][2] [3][4][5]ABCfront rearA Full Tank Please[0][1][2] [3][4][5]ABCfront rearDA Full Tank Please[0][1][2] [3][4][5]ABCfront rearD EA Full Tank Please[0][1][2] [3][4][5]ABCfront rearD EF•When a series of adds causes the queue to become full, front = rear.•So we cannot distinguish between a full queue and an empty queue!Ouch!!!!!•Remedies.Don’t let the queue get full.•When the addition of an element will cause the queue to be full, increase array size.•This is what the text does.Define a boolean variable lastOperationIsPut.•Following each put set this variable to true.•Following each remove set to false.•Queue is empty iff (front == rear) && !lastOperationIsPut•Queue is full iff (front == rear) && lastOperationIsPutOuch!!!!!•Remedies (continued).Define an integer variable size.•Following each put do size++.•Following each remove do size--.•Queue is empty iff (size == 0)•Queue is full iff (size == queue.length) Performance is slightly better when first strategy is


View Full Document

UF COP 3530 - Queues

Download Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?