Topic 16 QQueues "FISH queue: n.[acronym, by analogy with FIFO (First In, First Out)] ‘First In, Still Here’. A joking way of pointing out that processing of a particular sequence of events or requests has stopped dead Also FISH mode and FISHnet; thedead. Also FISH mode and FISHnet; the latter may be applied to any network that is running really slowly or exhibiting extremerunning really slowly or exhibiting extreme flakiness."-The Jargon File 4.4.7CS 307 Fundamentals of Computer Science Queues1gQueuesSi il t St kSimilar to StacksLike a line–In Britain people don’t “get in line” they“queue up”.they queue up.CS 307 Fundamentals of Computer Science Queues2Queue PropertiesQueues are a first in first out data structure– FIFO (or LILO, but that sounds a bit silly)Add items to the end of the queueAccess and remove from the frontAccess and remove from the front– Access to the element that has been in the structure the longest amount of timegUsed extensively in operating systemsQueues of processes I/O requests and much–Queues of processes, I/O requests, and much moreCS 307 Fundamentals of Computer Science Queues3Queues in Operating SystemsOih1CPUb hOn a computer with 1 CPU, but many processes how many processes can actually use the CPU at a time?O jbfOS hdlth f thCPUOne job of OS, schedule the processes for the CPUissues: fairness, responsiveness, progressCS 307 Fundamentals of Computer Science Queues4Queue operationsadd(Object item)– a.k.a. enqueue(Object item)Object get()–a.k.a. Object front(), Object peek()jjpObject remove()–akaObject dequeue()a.k.a. Object dequeue()boolean isEmpty()Sifi itf ll idSpecify in an interface, allow varied implementationsCS 307 Fundamentals of Computer Science Queues5Queue interface, version 1public interface Queue{ //place item at back of this Queueenqueue(Object item);q(j );//access item at front of this queue//pre: !isEmpty()//pre: !isEmpty()Object front();//remove item at front of this queue//pre: !isEmpty()Object dequeue();j q ();boolean isEmpty();}CS 307 Fundamentals of Computer Science Queues6}Implementing a QueueGi th i t l t t i dGiven the internal storage container and choice for front and back of queue what are th Bi O f th ti ?the Big O of the queue operations?ArrayList LinkedListLinkeListArrayList LinkedListLinkeList(Singly Linked) (Doubly Linked)enqueuefrontdequeuedequeueisEmptyCS 307 Fundamentals of Computer Science Queues7Attendance Question 1If implementing a queue with a singly linked list with references to the first and last nodes (head and tail) which end of the list should be the front of the queue in order to have all O( )?queue operations O(1)?A. The front of the list should be the front of the queueB. The back of the list should be the front of the queue.C. D. E. I don’t know, but I am sure looking forwardt t ki 307 i tiCS 307 Fundamentals of Computer Science Queues8to taking 307 again some time.Alternate ImplementationHow about implementing a Queue with a native array?– Seems like a step backwardsCS 307 Fundamentals of Computer Science Queues9Application of QueuesRdi S tRadix Sort– radix is a synonym for base. base 10, base 2M lti ti l ith th tllkMulti pass sorting algorithm that onlylooks at individual digits during each passUbkttt l tUse queues as bucketsto store elementsCreate an array of 10 queuesStarting with the least significant digit place value in queue that matches digitempty queues back into arrayrepeat, moving to next least significant digitCS 307 Fundamentals of Computer Science Queues10pg ggRadix Sort in Action: 1soriginal values in array113, 70, 86, 12, 93, 37, 40, 252, 7, 79, 12Look at ones place113, 70, 86, 12, 93, 37, 40, 252, 7, 79, 12,,,,,,,,,,Queues:070405070, 40516 86212252127377212, 252, 127 37, 73 113, 93 849979CS 307 Fundamentals of Computer Science Queues1149 9, 79Radix Sort in Action: 10sEt i df 0t9bkitEmpty queues in order from 0 to 9 back into array70401225212113938637797970, 40, 12, 252, 12, 113, 93, 86, 37, 7, 9, 79Now look at 10's place70401225212113938637797970, 40, 12, 252, 12, 113, 93, 86, 37, 7, 9, 79Queues:079525207, 9 5 252 112, 12, 113 6 27707927 70, 79 337 8 86440993CS 307 Fundamentals of Computer Science Queues12440 9 93Radix Sort in Action: 100sEidf09bkiEmpty queues in order from 0 to 9 back into array7, 9, 12, 12, 113, 37, 40, 252, 70, 79, 86, 93N l k t 100' lNow look at 100's place__7, __9, _12, _12, 113, _37, _40, 252, _70, _79, _86, _93QQueues:0 7, 9, _12, _12, _40, _70, _79, _86, _93 5 111361113 6 2252 7 383849CS 307 Fundamentals of Computer Science Queues13Radix Sort in Action: Final StepEmpty queues in order from 0 to 9 back into array7, 9, 12, 12, 40, 70, 79, 86, 93, 113, 252CS 307 Fundamentals of Computer Science Queues14Radix Sort Codepublic static void sort(int[] list){public static void sort(int[] list){ArrayList<Queue<Integer>> queues = new ArrayList<Queue<Integer>>();for(int i = 0; i < 10; i++)queues.add( new LinkedList<Integer>() );int passes=numDigits( list[0] );int passes numDigits( list[0] );int temp;for(int i = 1; i < list.length; i++){temp = numDigits(list[i]);if( temp > passes )if( temp > passes )passes = temp;}for(int i = 0; i < passes; i++){for(int j=0;j<list.length;j++){for(int j 0; j < list.length; j++){queues.get(valueOfDigit(list[j], i)).add(list[j]);}int pos = 0;for(Queue<Integer>q:queues){for(Queue<Integer> q : queues){while( !q.isEmpty())list[pos++] = q.remove();} }CS 307 Fundamentals of Computer Science
View Full Document
Unlocking...