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 Queues1gQueues8Si il t St k8Similar to Stacks8Like a line–In Britain people don’t “get in line” they“queue up”.they queue up .CS 307 Fundamentals of Computer Science Queues2Queue Properties88Queues are a first in first out data structure– FIFO (or LILO, but that sounds a bit silly)8Add items to the end of the queue8Access and remove from the frontAccess and remove from the front– Access to the element that has been in the structure the longest amount of timeg8Used 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 Systems8Oih1CPUb h8On a computer with 1 CPU, but many processes how many processes can actually use the CPU at a time?8O jbfOS hdlth f thCPU8One job of OS, schedule the processes for the CPU8issues: fairness, responsiveness, progressCS 307 Fundamentals of Computer Science Queues4Queue operations88add(Object item)– a.k.a. enqueue(Object item)8Object get()–a.k.a. Object front(), Object peek()jjp8Object remove()–akaObject dequeue()a.k.a. Object dequeue()8boolean isEmpty()8Sifi itf ll id8Specify 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 Queue8Gi th i t l t t i d8Given 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 188If 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 Implementation88How about implementing a Queue with a native array?– Seems like a step backwardsCS 307 Fundamentals of Computer Science Queues9Application of Queues8Rdi S t8Radix Sort– radix is a synonym for base. base 10, base 28M lti ti l ith th tllk8Multi pass sorting algorithm that onlylooks at individual digits during each pass8Ubkttt l t8Use queues as bucketsto store elements8Create an array of 10 queues8Starting with the least significant digit place value in queue that matches digit8empty queues back into array8repeat, moving to next least significant digitCS 307 Fundamentals of Computer Science Queues10pg ggRadix Sort in Action: 1s88original values in array113, 70, 86, 12, 93, 37, 40, 252, 7, 79, 128Look at ones place113, 70, 86, 12, 93, 37, 40, 252, 7, 79, 12,,,,,,,,,,8Queues:070405070, 40516 86212252127377212, 252, 127 37, 73 113, 93 849979CS 307 Fundamentals of Computer Science Queues1149 9, 79Radix Sort in Action: 10s8Et i df 0t9bkit8Empty queues in order from 0 to 9 back into array70401225212113938637797970, 40, 12, 252, 12, 113, 93, 86, 37, 7, 9, 798Now look at 10's place70401225212113938637797970, 40, 12, 252, 12, 113, 93, 86, 37, 7, 9, 798Queues: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: 100s8Eidf09bki8Empty queues in order from 0 to 9 back into array7, 9, 12, 12, 113, 37, 40, 252, 70, 79, 86, 938N l k t 100' l8Now look at 100's place__7, __9, _12, _12, 113, _37, _40, 252, _70, _79, _86, _938Q8Queues: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 Step88Empty 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...