Transcript Queues

CSCI 3333 Data Structures
Queues
by
Dr. Bun Yue
Professor of Computer Science
[email protected]
http://sce.uhcl.edu/yue/
2013
Acknowledgement




Mr. Charles Moen
Dr. Wei Ding
Ms. Krishani Abeysekera
Dr. Michael Goodrich
Queues

First In First Out (FIFO) data
structure.
Queues




The Queue ADT stores arbitrary objects
Insertions and deletions follow the first-in
first-out scheme
Insertions are at the rear of the queue
and removals are at the front of the
queue
Main queue operations:


enqueue(object): inserts an element at the
end of the queue
object dequeue(): removes and returns the
element at the front of the queue
Queue Operations

Some auxiliary queue operations:




object front(): returns the element at the front
without removing it
integer size(): returns the number of elements
stored
boolean isEmpty(): indicates whether no
elements are stored
Exceptions

Attempting the execution of dequeue or front
on an empty queue throws an
EmptyQueueException
Queue Example
Operation
enqueue(5)
enqueue(3)
dequeue()
enqueue(7)
dequeue()
front()
dequeue()
dequeue()
isEmpty()
enqueue(9)
enqueue(7)
size()
enqueue(3)
enqueue(5)
dequeue()
Output Q
–
(5)
–
(5, 3)
5
(3)
–
(3, 7)
3
(7)
7
(7)
7
()
“error” ()
true
()
–
(9)
–
(9, 7)
2
(9, 7)
–
(9, 7, 3)
–
(9, 7, 3, 5)
9
(7, 3, 5)
Queue Interface in Java


Not a class!
Super-interfaces:



Collection<E>
Iterable<E>
Sub-interfaces:


BlockingDeque<E>: waits for queue to
become non-empty when dequeue.
Deque<E>
Known Implementations of Queue











AbstractQueue
ArrayBlockingQueue
ArrayDeque
ConcurrentLinkedQueue
DelayQueue
LinkedBlockingDeque
LinkedBlockingQueue
LinkedList
PriorityBlockingQueue
PriorityQueue
SynchronousQueue
Some Implementation Criteria

As queues are general data
structures for widespread use, there
are variations to fit different
applications. Some considerations:





Implementation: array vs. linked list.
Thread safe or not.
Blocking or not.
Synchronous or not: i.e. rendezvous in
Ada
Allow null elements or not.
Applications of Queues

Some direct applications







Waiting lists, bureaucracy
Access to shared resources (e.g., printer)
Simulation
Breadth-first traversals
Multiprogramming
Messaging
Indirect applications


Auxiliary data structure for algorithms
Component of other data structures
Array-based Queue


Use an array of size N in a circular fashion
Two variables keep track of the front and rear
f index of the front element
r index immediately past the rear element

Array location r is kept empty
normal configuration
Q
0 1 2
f
r
wrapped-around configuration
Q
0 1 2
r
f
Queue Operations

We use the
modulo operator
(remainder of
division)
Algorithm size()
return (N - f + r) mod N
Algorithm isEmpty()
return (f = r)
Q
0 1 2
f
0 1 2
r
r
Q
f
Queue Operations (cont.)


Operation enqueue
throws an exception if
the array is full
This exception is
implementationdependent
Algorithm enqueue(o)
if size() = N - 1 then
throw FullQueueException
else
Q[r]  o
r  (r + 1) mod N
Q
0 1 2
f
0 1 2
r
r
Q
f
Queue Operations (cont.)


Operation dequeue
throws an exception
if the queue is empty
This exception is
specified in the
queue ADT
Algorithm dequeue()
if isEmpty() then
throw EmptyQueueException
else
o  Q[f]
f  (f + 1) mod N
return o
Q
0 1 2
f
0 1 2
r
r
Q
f
Queue Interface in Java



Java interface
corresponding to
our Queue ADT
Requires the
definition of class
EmptyQueueException
No corresponding
built-in Java class
public interface Queue {
public int size();
public boolean isEmpty();
public Object front()
throws EmptyQueueException;
public void enqueue(Object o);
public Object dequeue()
throws EmptyQueueException;
}
Linked List Implementation

We have already implemented
methods necessary for the queue
ADT (under different method
names) using a singly linked list.
Application: Round Robin Schedulers

We can implement a round robin scheduler using a
queue, Q, by repeatedly performing the following
steps:
1.
2.
3.
e = Q.dequeue()
Service element e
Q.enqueue(e)
The Queue
1. Deque the
next element
2 . Service the
next element
Shared
Service
3. Enqueue the
serviced element
Palindrome in C++: Spot the error
#include “Stack.h”;
#include “Queue.h”;
#include <iostream.h>
using namespace std;
int main() {
// Incorrect solution. Can you see it?
Stack
S;
Queue
Q;
char ch;
cout << “Enter string to be tested as palindrome: “;
while (cin >> ch) {
S.push(ch);
Q.enqueue(ch);
}
bool pal = true;
while (!Q.isEmpty())
pal = Q.dequeue() == S.pop();
if (pal)
cout << “Palindrome!!” << endl;
return EXIT_SUCCESS; }
Example: Queue in Ruby



Ruby is a newer object oriented
scripting language using some
software engineering principles.
We use a queue example in Ruby to
illustrative the use of queues for
concurrent processes.
There is no need to understand all
details of the example.
Queue.rb
require 'thread'
queue = Queue.new
producer = Thread.new do
# concurrent thread 1
5.times do |i|
sleep rand(i) # simulate expense
queue << i
puts "#{i} produced"
end
end
consumer = Thread.new do
# concurrent thread 2
5.times do |i|
value = queue.pop
sleep rand(i/2) # simulate expense
puts "consumed #{value}"
end
end
consumer.join
Executing Queue.rb
0 produced
1 produced
consumed 0
2 produced
consumed 1
consumed 2
3 produced
consumed 3
4 produced
consumed 4
Discussion

Similar operations because of
similar ADT




new
<< (push): enqueue
pop: dequeue
“thread-safe”
Questions and Comments?