Transcript 06. Queues

241-423 Advanced Data Structures
and Algorithms Semester 2, 2013-2014
6. Queues
• Objective
– implement queues, bounded queues, and
priority queues. Explain Radix sort.
ADSA: Queues/6
1
Contents
1.
2.
3.
4.
5.
The Queue Collection
Interview Scheduler
Radix Sort
A Bounded Queue
Priority Queue Collection
ADSA: Queues/6
2
1. The Queue Collection
• A queue is a list of items, where items can only
•
enter the queue at the back and exit from the front.
Elements leave a queue in the same order as they
enter
– a queue has a First-In-First-Out (FIFO) ordering
ADSA: Queues/6
3
The Queue Interface
interface Queue<T>
ds.util
boolean isEmpty()
Returns true if this collection contains no
elements and false if the collection has at least 1
element.
T peek()
Refer to element at the front of the queue. If
empty, throws a NoSuchElementException.
ADSA: Queues/6
continued
4
interface Queue<T>
ds.util
T pop()
Removes the element at the front of the queue
and returns its value. If the queue is empty,
throws a NoSuchElementException.
void push(T item)
Inserts item at the back of the queue.
int size()
Returns the number of elements in this queue
ADSA: Queues/6
5
The LinkedQueue Class
public class LinkedQueue<T> implements Queue<T>
{
private LinkedList<T> qlist;
public LinkedQueue ()
{ qlist = new LinkedList<T>();
LinkedQueue
implements the Queue
interface using the
LinkedList class
}
/* implementations of isEmpty(), peek(),
pop(), push(), size() using qlist
*/
:
ADSA: Queues/6
6
pop() has runtime
efficiency O(1)
public T pop()
{
if (isEmpty())
throw new NoSuchElementException(
"LinkedQueue pop(): queue empty");
// remove and return first element in list
return qlist.removeFirst();
}
}
// end of LinkedQueue class
ADSA: Queues/6
7
2. Interview Scheduler
• The interview scheduler is a queue of
Time24 objects. It outputs a list of the times
and the potential length of each interview.
ADSA: Queues/6
8
Execution
(4:30 + 0:30 == 5pm, the end of the day)
ADSA: Queues/6
9
import java.io.*;
import java.util.Scanner;
import ds.util.LinkedQueue;
import ds.time.Time24;
public class InterviewScheduler
{
public static void main(String[] args)
throws IOException
{
Time24 END_DAY = new Time24(17,00);
// read times from "appt.txt"
Scanner input = new Scanner(
new FileReader("appt.txt") );
:
ADSA: Queues/6
10
// create a queue for the appointment times
LinkedQueue<Time24> apptQ =
new LinkedQueue<Time24>();
while (input.hasNext()) {
String apptStr = input.nextLine();
// read time
apptQ.push( Time24.parseTime(apptStr) );
// add time to queue
}
// output the day's appointment schedule
System.out.println("Appointment
Interview");
:
ADSA: Queues/6
11
Time24 apptTime, interviewTime;
while (!apptQ.isEmpty()) {
apptTime = apptQ.pop(); // get next appointment
/* interview time is time to next
appointment or to END_DAY */
if (!apptQ.isEmpty())
interviewTime = apptTime.interval( apptQ.peek());
else
interviewTime = apptTime.interval(END_DAY);
System.out.println("
"
}
}
" + apptTime +
" + interviewTime);
}
// end of main()
// end of InterviewScheduler class
ADSA: Queues/6
12
3. Radix Sort
• Radix sort uses the digits in each array element
to sort the array.
• The array elements are passed to ten queues
(index 0 to 9) using each element's digit as the
index.
• Elements are copied from the queues back to
the original array, in partially sorted order.
ADSA: Queues/6
13
Radix Sort Example
• Array: [91, 6, 85, 15, 92, 35, 30, 22, 39]
use the units
digit in each element
(100 digit)
After Pass 0: [30, 91, 92, 22, 85, 15, 35, 6, 39]
partially
sorted
use the tens
digit in each element
(101 digit)
After Pass 1: [6, 15, 22, 30, 35, 39, 85, 91, 92]
ADSA: Queues/6
fully
sorted
continued
14
• The i-th pass distributes the array elements
into one of the 10 queues by looking at the
digit in each element corresponding to the
power 10i.
– in pass 0, look at units digit (100)
– in pass 1, look at tens digit (101)
ADSA: Queues/6
continued
15
• Radix sort must carry out d passes, one for
each digit in the largest element
– e.g. if the largest element is 92, then d = 2 passes;
if largest is142, then d == 3 passes
ADSA: Queues/6
16
Radix Sort Methods
public static void radixSort(int[] arr, int radix)
{
// create a 10 elem LinkedQueue array
LinkedQueue[] digitQueues = new LinkedQueue[10];
// initialize digitQueues to hold empty queues
for (i=0; i < digitQueues.length; i++)
digitQueues[i] = new LinkedQueue();
// current digit found by dividing by power
int power = 1;
// will increase in 10's
for (int i=0; i < radix; i++) {
distribute(arr, digitQueues, power);
collect(digitQueues, arr);
power *= 10;
}
}
ADSA: Queues/6
17
private static void distribute(int[] arr,
LinkedQueue[] digitQueues, int power)
// distribute array elements between 10 queues
{
for (int i = 0; i < arr.length; i++) {
int digit = (arr[i] / power) % 10;
// get digit from element
digitQueues[digit].push( arr[i] );
/* use digit to decide which queue
should hold the element */
}
}
ADSA: Queues/6
18
private static void collect(LinkedQueue[] digitQueues,
int[] arr)
// copy elements from the queues back to the array
{
int i = 0;
// scan the array of queues
for (int digit = 0; digit < 10; digit++)
while (!digitQueues[digit].isEmpty()) {
arr[i] = digitQueues[digit].pop();
// queue-->arr
i++;
}
}
ADSA: Queues/6
19
Using Radix Sort
import java.util.Random;
import ds.util.Arrays;
public class UseRadixSort
{
public static void main(String[] args)
{
int[] arr = new int[50];
// 50-element array
Random rnd = new Random();
for (int i = 0; i < 50; i++)
arr[i] = rnd.nextInt(100000);
// random nos: 0 to 99999
}
Arrays.radixSort(arr, 5);
displayArray(arr);
// end of main()
ADSA: Queues/6
// 5 digits in 99999
20
private static void displayArray(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
String s = String.valueOf(arr[i]); // int --> string
// right justify s inside 8 char positions
String just = "";
for (int j=0; j < 8-s.length(); j++)
just += " ";
just += s;
System.out.print(just);
if ((i+1) % 6 == 0) // newline every 6 numbers
System.out.println();
}
}
}
System.out.println();
// end of displayArray()
// end of UseRadixSort
ADSA: Queues/6
21
Execution
ADSA: Queues/6
22
Radix Sort Efficiency
• The runtime efficiency of radixSort() is
O(radix*n) where the list has n elements and
the biggest element has radix digits
– a fast linear sorting algorithm
• But radixSort() uses a lot of memory
– it needs one queue for each digit
• If we are sorting strings, then we will need 1
queue for each different letter (62+ queues)
ADSA: Queues/6
23
4. A Bounded Queue
• A bounded queue is a queue that has a
maximum size (capacity).
• A queue insertion can only occur when the
queue is not full.
ADSA: Queues/6
24
The BQueue Class
• The BQueue class represents a bounded
queue.
• The class implements the Queue interface
using an array to store the elements
– an array is okay since the bounded queue has a
maximum capacity
ADSA: Queues/6
25
BQueue Class API
interface BQueue<T> implements Queue
ds.util
BQueue()
Creates a queue with fixed size 50.
BQueue(int size)
Creates a queue with specified fixed size.
boolean full()
Returns true if the number of elements in the
queue equals is fixed size and false otherwise.
and the other methods in the Queue interface
ADSA: Queues/6
26
BQueue Class Example
// declare an empty bounded queue with capacity 15
BQueue<Integer> q = new BQueue<Integer>(15);
for (int i=1; !q.full(); i++)
q.push(i);
// fill the queue
// print element at the q front, and queue size
System.out.println(q.peek() + ", " + q.size());
try {
q.push(40);
// try to add 40 to full bqueue
}
catch (IndexOutOfBoundsException e)
{ System.out.println(e); }
1, 15
java.lang.IndexOutOfBoundsException: BQueue push(): queue full
ADSA: Queues/6
27
BQueue Class
public class BQueue<T> implements Queue<T>
{
private T[] queueArray;
// array for queue elements
// index of front and back of queue
private int qfront, qback;
// queue capacity, and current size
private int qcapacity, qcount;
public BQueue(int size)
// create an empty bounded queue with the specified size
{
queueArray = (T[])new Object[size];
qfront = 0; qback = 0;
qcapacity = size; qcount = 0;
}
ADSA: Queues/6
28
public BQueue()
// a bounded queue of max size 50
{ BQueue(50); }
// method full() and other methods in the Queue interface
}
// end of BQueue class
ADSA: Queues/6
29
BQueue Class Implementation
No room for E.
Need a way to use
the slots at indices 0, 1.
ADSA: Queues/6
continued
30
• Think of the queue as a circular sequence.
• Element are added in a clockwise order.
– the element at index qfront exits the queue
– an element enters the queue at index qback.
ADSA: Queues/6
continued
31
• qfront and qback 'cycle back' to the front of the array
when they move off the end of the array.
Move qback forward:
Move qfront forward:
ADSA: Queues/6
qback = (qback + 1) % qcapacity;
qfront = (qfront + 1) % qcapacity;
32
Testing if the bQueue is Full
• The bqueue is full when every box of the
array is full.
• The easiest way to detect this is to store the
bqueue's current size (qcount) and
maximum capacity (qcapacity), and test if
they are equal.
• qcount will increase when an element is
added, decrease when one is removed.
ADSA: Queues/6
33
BQueue Class full()
public boolean full()
{
return (qcount == qcapacity);
}
ADSA: Queues/6
34
BQueue Class push()
public void push(T item)
{
// is queue full?
if (qcount == qcapacity)
throw new IndexOutOfBoundsException(
"BQueue push(): queue full");
queueArray[qback] = item;
qback = (qback+1) % qcapacity;
}
// insert item
// move qback forward
qcount++;
// increment the queue size
// end of push()
ADSA: Queues/6
35
BQueue Class pop()
public T pop()
{
// is queue empty?
if (count == 0)
throw new NoSuchElementException(
"BQueue pop(): empty queue");
// temporarily store the front item
T item = queueArray[qfront];
// move qfront forward, so front element is 'deleted'
qfront = (qfront+1) % qcapacity;
qcount--;
}
// decrement the queue size
return item;
// return the old front item
// end of pop()
ADSA: Queues/6
36
5. Priority Queue Collection
• In a priority queue, all the elements have priority
•
values.
A deletion always removes the element with the
highest priority.
ADSA: Queues/6
37
PQueue Interface
• The generic PQueue resembles a queue
with the same method names.
interface PQueue<T>
ds.util
boolean isEmpty()
Returns true if the priority queue is empty and
false otherwise.
T peek()
Refer to value of the highest-priority item. If
empty, throws a NoSuchElementException.
ADSA: Queues/6
continued
38
interface PQueue<T>
ds.util
T pop()
Removes the highest priority item from the
queue and returns its value. If it is empty,
throws a NoSuchElementException.
void push(T item)
Inserts item into the priority queue.
int size()
Returns the number of elements in this
priority queue
ADSA: Queues/6
39
HeapPQueue Class
• The collection class HeapPQueue implements
the PQueue interface, using a Heap data
structure which I'll explain in a later part.
ADSA: Queues/6
40
HeapPQueue Class Example
// create a priority queue of Strings
HeapPQueue<String> pq = new HeapPQueue<String>();
pq.push("green");
pq.push("red");
The priority for Strings
pq.push("blue");
is alphabetical order
// output the size, and element with highest priority
System.out.println(pq.size() + ", " + pq.peek());
// use pop() to empty the pqueue and list elements
// in decreasing priority order
while ( !pq.isEmpty() )
System.out.print( pq.pop() + " ");
3, red
red green
ADSA: Queues/6
blue
41