Transcript Queue

Queues
• What is queues?
• Queue Implementation Using Linked Lists.
• Applications of Queues.
What is a queue?
• Queues are linear data structures in which we add elements to one
end and remove them from the other end.
• The first item to be en-queued is the first to be de-queued. Queue
are therefore called a FIFO structure.
• Queue operations:
Enqueue
Dequeue
GetFrontItem
What is a queue?
Rear
Front
4
1
3
4
1
3
4
1
3
4
1
enqueue(1);
1
Given the following Queue, how will it
change when we apply the given
operations?
enqueue(5);
5
1
dequeue();
5
1
dequeue();
5
1
4
dequeue();
5
1
Queue Implementation
•
•
In our implementation, a queue is a container that extends the
AbstractContainer class and implements the Queue interface.
MyLinkedList is used here as the Underlying data structure.
public interface Queue extends Container{
public abstract Object getHead();
public abstract void enqueue(Object obj);
public abstract Object dequeue();
}
Queue Implementation - Constructor
• The queue uses an instant variable, list, of type MyLinkedList.
• The constructor creates an empty list and assigned it to the instance
variable.
import java.util.NoSuchElementException;
public class QueueAsLinkedList extends AbstractContainer
implements Queue {
protected MyLinkedList list;
public QueueAsLinkedList(){
list = new MyLinkedList();
}
Queue Implementation - purge() & getHead()
methods
public void purge() {
list.purge();
count = 0;
}
public Object getHead(){
if(count == 0)
throw new ContainerEmptyException();
else
return list.getFirst();
}
Queue Implementation – enqueue() & dequeue()
methods
public void enqueue(Object obj){
list.append(obj);
count++;
}
public Object dequeue(){
if(count == 0)
throw new ContainerEmptyException();
else{
Object obj = list.getFirst();
list.extractFirst();
count--;
return obj;
}
}
Queue Implementation - getEnumeration method
public Enumeration getEnumeration(){
return new Enumeration() {
MyLinkedList.Element position = list.getHead();
public boolean hasMoreElements(){
return position != null;
}
public Object nextElement(){
if(position == null)
throw new NoSuchElementException();
else{
Object obj = position.getDatum();
position = position.getNext();
return obj;
}
}
};
}
protected int compareTo(MyComparable comparable){
throw new MethodNotImplemented();
}
}
Application of Queues
• Direct applications
– Waiting lines: Queues are commonly used in systems
where waiting line has to be maintained for obtaining
access to a resource. For example, an operating
system may keep a queue of processes that are
waiting to run on the CPU.
– Access to shared resources (e.g., printer)
– Multiprogramming
• Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
Application of Queues: Testing for palindromes
• A palindrome is a string that reads the same forwards as backwards.
• Some palindromes are:
– "A man, a plan, a canal, Panama"
– "Madam, I'm Adam“
– "Eve“
– "mom“
– "dad“
– "Madam“
– "202“
– "SMS.
Application of Queues: Testing for palindromes
public static boolean isPalindrome(String s) {
StackAsLinkedList stack = new StackAsLinkedList();
QueueAsLinkedList queue = new QueueAsLinkedList();
s = s.toLowerCase();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch) || Character.isLetter(ch)) {
stack.push(new Chr(ch));
queue.enqueue(new Chr(ch));
}
}
Chr char1, char2;
while(!stack.isEmpty()) {
char1 = (Chr) stack.pop();
char2 = (Chr) queue.dequeue();
if(char1.isNE(char2))
return false;
}
return true;
}
Priority Queues
• In a normal queue the enqueue operation add an item at the back of
the queue, and the dequeue operation removes an item at the front
of the queue.
• A priority queue is a queue in which the dequeue operation removes
an item at the front of the queue; but the enqueue operation insert
items according to their priorities.
• A higher priority item is always enqueued before a lower priority
element.
• An element that has the same priority as one or more elements in
the queue is enqueued after all the elements with that priority.