Unit 7: Queues (Aston University)

✎ Unit 7: Queues Unit Objectives. Here you will: learn how to implement a queue ADT using a ‘circular’ array learn about priority queues learn how to implement a priority queue using: ⋄ a linked list ⋄ an array of FIFO queues...

✎ Unit 7: Queues Unit Objectives. Here you will: learn how to implement a queue ADT using a ‘circular’ array learn about priority queues learn how to implement a priority queue using: ⋄ a linked list ⋄ an array of FIFO queues describe the time implication of performing queue operations using the Big-O notation consider implementations of queue in the JCF. SHS Wong DSA 7.Queues 1/42 ✎ An Array Implementation of QueueADT An array-based implementation of the bounded queue ADT with the front of the queue fixed at index 0 has a drawback: ➠ The time complexity of the dequeue method was O(n). Why? The array elements from index 1 onwards will need to be shifted one place ‘down’ to fill the gap at index 0. SHS Wong DSA 7.Queues 2/42 ✎ Another Array Implementation of QueueADT Is there a way to use an array to implement a queue ADT without having to perform shifting? ➠ Yes! If we do not fix one end of the queue at index 0, we will not have to shift the elements... ➠ A circular queue (or circular buffer) utilises an array that conceptually wraps around on itself: ➠ The last index is thought to be followed by index 0. SHS Wong DSA 7.Queues 3/42 ✎ Class CircularArrayQueue A B 0 1 C... 2 7 3 6 5 4 D 0 4 front rear We keep track of two integers for indicating the front and rear of the queue at any given time. To distinguish between empty and full queues where front & rear are equal, we may record the size of the queue in count. SHS Wong DSA 7.Queues 4/42 ✎ Cirular Queues SHS Wong DSA 7.Queues 5/42 ✎ Class CircularArrayQueue 1 public class CircularArrayQueue 2 implements QueueADT { 3 4 private final int DEFAULT = 100; 5 private 6 7 // index of first element 8 private int 9 10 // index of next available slot 11 private int 12 13 private int 14 15 16 17 18 19 20 21 22 } SHS Wong DSA 7.Queues 6/42 ✎ Circular Queue: enqueue When an element is enqueued, it is stored at index rear. rear is then incremented. But we must allow for looping back to 0: rear = (rear+1) % queue.length; Also the array can reach its full capacity and may need enlarging. 1 public void enqueue (T element) { 2 if (size() == queue.length) 3 expandCapacity(); 4 5 queue[rear] = element; 6 rear = (rear+1) % queue.length; 7 8 count++; 9 } SHS Wong DSA 7.Queues 7/42 ✎ Unbounded Cirular Queues: expand capacity Original circular array A New, larger circular array G B D D 9 0 D 14 15 16 1 13 17 C 12 18 8 11 2 19 10 7 C 9 0 F 3 8 1 6 2 4 7 3 5 B 6 5 4 H D B A B D G F H D 5 5 0 10 front rear front rear SHS Wong DSA 7.Queues 8/42 ✎ Circular Queue: expandCapacity 1 private void expandCapacity() { 2 T[] larger = (T[])(new Object[queue.length *2]); 3 4 for(int scan=0; scan < count; scan++) { 5 larger[scan] = queue[front]; 6 front = (front+1) % queue.length; 7 } 8 front = 0; 9 rear = count; 10 queue = larger; 11 } When existing elements are copied to the enlarged array, they are copied to the start of the enlarged array so that the front is again at index 0. SHS Wong DSA 7.Queues 9/42 ✎ Circular Queue: dequeue When an element is dequeued, it is retrieved from index front. front is then incremented. ➠ We will also need to take care of the ‘looping back’, i.e.: front = (front+1) % queue.length; 1 public T dequeue() { 2 if (isEmpty()) 3 throw new IllegalStateException("queue empty"); 4 5 T result = queue[front]; 6 queue[front] = null; 7 front = (front+1) % queue.length; 8 count--; 9 return result; 10 } SHS Wong DSA 7.Queues 10/42 ✎ Analysis of (Unbounded) Queue Operations Normal Worst Linked implementation: ⋄ enqueue: ⋄ dequeue: Linear Array implementation: ⋄ enqueue: ⋄ dequeue: Circular Array implementation: ⋄ enqueue: ⋄ dequeue: ➟ Linked implementation is most efficient, but it has higher storage overhead. SHS Wong DSA 7.Queues 11/42 Some ✎ Uses of Queues: multi-threaded software applications Queues are often used in multi-threaded software applications. Data items for processing are produced by ‘producer’ threads and deposited in a queue from where they are retrieved later by ‘consumer’ threads and processed. ➡ The execution of the producer and consumer threads is largely decoupled. If at a certain time the producers are producing data faster than it can be consumed, the producers do not have to wait, they simply add their data items to the queue. When the consumers start to consume data faster than it can be produced, they will not be delayed as they can retrieve data items from the backlog in the queue. SHS Wong DSA 7.Queues 12/42 ✎ Some Uses of Queues: ticket counter simulation Queues are often used in simulations to model real-life queues. A typical use of a queue is to simulate a waiting line. ⋄ Consider a waiting line at a ticket booth. ⋄ The goal is to determine how many cashiers are needed to keep the wait time < 7 minutes. ⋄ We will assume: · customers arrive on average every 15 seconds · processing a request takes 2 minutes once a customer reaches a cashier SHS Wong DSA 7.Queues 13/42 ✎ Ticket Counter Simulation: a UML description SHS Wong DSA 7.Queues 14/42 ✎ Ticket Counter Simulation: Algorithm Simulate the ticket counter scenario using various numbers of cashiers: 1. Create the customer waiting queue. ➠ Each customer keeps track of their arrival and departure times. Assumption: Customers arrive on average every 15 seconds. 2. Each cashier needs to record the time they finished serving the last customer. ➠ Modelled by an array of type int[] named cashiers. ➠ At the start of the simulation, each cashier is available at time 0 second. Assumption: Each cashier takes 2 minutes to serve one customer: final static int PROCESS = 120; SHS Wong DSA 7.Queues 15/42 ✎ Ticket Counter Simulation: Algorithm 3. Process all customers in the queue: (a) Each cashier takes turn to serve a customer in the waiting queue. ➠ If a customer arrives at a time when the cashier is busy, they will need to wait: customer’s departure = cashier’s last service + process time completion time time ➠ If a customer arrives at a time when the cashier is free, no waiting is required: customer’s departure = customer’s arrival + process time time time (b) Update the cashier’s time accordingly. SHS Wong DSA 7.Queues 16/42 ✎ Ticket Counter Simulation: Algorithm 3. Process all customers in the queue (Cont’d): (c) Accumulate the time that each customer actually spent at the ticket center: customer’s time = customer’s departure - customer’ spent at the ticket time arrival booth time 4. Output the average time that each customer spent at the ticket center. SHS Wong DSA 7.Queues 17/42 ✎ Ticket Counter Simulation: Java code 1 public static void main ( String[] args) { 2 3 LinkedQueue customerQueue = new LinkedQueue(); 4 5 int[] cashierTime = new int[MAX_CASHIERS]; 6 7 int totalTime, averageTime, departs; 8 9 for (int cashiers=0; cashiers < MAX_CASHIERS; cashiers++) { 10 // initialises each cashier’s time of availability 11 for (int count=0; count < cashiers; count++) 12 cashierTime[count] = 0; 13 14 // creates a queue of customers 15 for (int count=1; count = elem.getPriority()) { 9 previous = current; 10 current = current.getNext(); 11 } 12 13 if (previous == null) { // insert node at front of queue 14 tmp.setNext(front); 15 front = tmp; 16 } else { // insert new node after previous node 17 tmp.setNext(previous.getNext()); 18 previous.setNext(tmp); 19 } 20 count++; 21 } SHS Wong DSA 7.Queues 26/42 ✎ LinkedPriorityQueue: dequeue The dequeue operation is practically the same as that in a standard FIFO queue. 1 public T dequeue() { 2 if (isEmpty()) { 3 throw new IllegalStateException("Queue empty"); 4 } 5 T item = front.getElement(); 6 7 // make front point to the new front node 8 front = front.getNext(); 9 count--; // decrement size 10 return item; 11 } SHS Wong DSA 7.Queues 27/42 ✎ How to implement an efficient priority queue? A simple array-based implementation of priority queue is inefficient. priorityQueue 0 1 2 3 4 5 6 7 8 9 null null null null null :Element :Element :Element :Element :Element priority 1 priority 2 priority 2 priority 3 priority 4............... A linked list based implementation of priority queue is slightly better, but not by much. :Element priority 2. front.. null :Element :Element :Element :Element priority 1 priority 2 priority 2 priority 4............ ➠ There is a simple technique which is appropriate if the number of priority levels is not too large. SHS Wong DSA 7.Queues 28/42 ✎ A Multi-Queue Implementation Suppose the priority levels are integers and range from 0 (lowest) to M (highest). We implement the priority queue as an array queueList of size M + 1 of ordinary FIFO queues. ⋄ An item is enqueued in the normal way on the FIFO queue corresponding to its priority level. ⋄ The method dequeue works by calling the dequeue method of the non-empty queue with the highest priority. SHS Wong DSA 7.Queues 29/42 ✎ Priority Queue: a Multi-Queue implementation queueList 0 1 2 3 4 5 null null null front null front null :Element :Element priority 4 priority 1.. front null.... :Element :Element priority 2 priority 2...... SHS Wong DSA 7.Queues 30/42 ✎ PriorityQueue.java 1 package dsaj; 2 public class PriorityQueue 3 implements QueueADT { 4 private QueueADT[] queueList; 5 // priorities run from 0.. maxPriority inclusive 6 private final int maxPriority; 7 private int count; 8 9 public PriorityQueue(int maxPriority) { 10 this.maxPriority = maxPriority; 11 queueList = (QueueADT[]) 12 Array.newInstance(QueueADT.class, maxPriority+1); 13 for (int i = 0; i