Describe the characteristics and applications of a queue.
Construct algorithms using the access methods of a queue.
Explain the use of arrays as static stacks and queues.
Describe the characteristics and applications of a queue.
A queue a data structure that stores a set of data elements in a particular order. Data elements in a queue are retrieved in the same order as they were stored. This access methods is called FIFO structure - First-In-First-Out.
Queue is controlled by two operations: add and remove (enqueue or dequeue)
enqueue() - inserts a data element at the rear/end of the queue
dequeue() - removes and returns the first data element entered in the queue
isEmpty - tests if a queue is empty and returns true if queue contains NO elements.
Queues are used to model physical queues, such as people waiting in line at a supermarket checkout.
The print queue displays the documents that are waiting to be printed. These documents will follow the first-send-print policy.
When sending data over the internet, various data packets wait in a queue to be sent.
A server usually serves various requests. In most cases these requests are stored in a queue. The first-come first-served request procedure is followed.
public class QueueInArray {
private int[] data;
private int front, rear, maxSize;
/**
* constructor
* pre: none
* post: An empty queue that can hold up to maxItems has been created.
*/
public QueueInArray(int maxItems) {
data = new int[maxItems];
front = -1; //no items in the array
rear = -1;
maxSize = maxItems;
}
/**
* Returns the front item without removing it from the queue.
* pre: Queue contains at least one item.
* post: The front item has been returned while leaving it in the queue.
*/
public int front() {
return (data[front]);
}
/**
* Removes the front item from the queue and returns it.
* pre: Queue contains at least one item.
* post: The front item of the queue has been removed and returned.
*/
public int dequeue() {
front = (front + 1) % maxSize;
System.out.println("dequeing..." + data[front-1]);
return (data[front-1]);
}
/**
* Adds an item to the queue if there is room.
* pre: none
* post: A new item has been added to the queue.
*/
public void enqueue(int num) {
if (isEmpty()) { //first item queued
rear = 0;
front = 0;
data[rear] = num;
System.out.println("queing..." + data[rear]);
} else {
rear = (rear + 1) % maxSize;
data[rear] = num;
System.out.println("queing..." + data[rear]);
}
}
/**
* Determines if there are items on the queue.
* pre: none
* post: true returned if there are items on the queue, false returned otherwise.
*/
public boolean isEmpty() {
if (front == -1 && rear == -1) {
return (true);
} else {
return (false);
}
}
/**
* Returns the number of items in the queue.
* pre: none
* post: The number of items in the queue is returned.
*/
public int size() {
if (isEmpty()) {
return (0);
} else {
return (rear - front + 1);
}
}
/**
* Empties the queue.
* pre: none
* post: There are no items in the queue.
*/
public void makeEmpty() {
front = -1;
rear = -1;
}
/**
* Prints the contents of the queue with position of each item
*/
public void displayArray() {
for (int n = 0; n < data.length; n++) {
System.out.print(String.format(" %2s " + " ", n));
}
System.out.println();
for (int n = 0; n < data.length; n++) {
System.out.print(String.format(" %2s " + " ", data[n]));
}
System.out.println();
}
public class Queue<E> {
ArrayList<E> data;
int back, front;
public Queue() {
data = new ArrayList();
back = -1;
front = -1;
}
public void enqueue(E item) {
if (isEmpty()) {
front += 1;
}
back += 1;
data.add(item);
}
public E dequeue() {
if (!isEmpty()) {
E temp = data.get(front);
data.remove(front);
back--;
return temp;
}
return null;
}
public E front() {
if(!isEmpty())
return data.get(front);
return null;
}
public int size() {
return back + 1;
}
public boolean isEmpty() {
return back == -1 && front == -1;
}
public void makeEmpty(){
back = -1;
front = -1;
}
}