Queues are programmatic data structures that allow access to only one item at a time, the first item inserted. Queues internally use other data structures such as arrays for their implementation. A queue is a First-In-First-Out (FIFO) storage mechanism, because the first item inserted is the first to be removed.
Queues usually provide the following key interfaces.
insert() - Inserts a new data item oat the end of queue.
remove() - Removes the item from the end of the queue
peek() - Returns the item from the front of the queue without removing it.
isFull() - Returns true if the queue is full.
isEmpty() - Returns true if the queue is empty.
Following Java program implements the queue functionality. It internally uses an array for the implementation.
class MyQueue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int numberOfItems;
//constructor
public MyQueue(int maxSize) {
this.maxSize = maxSize;
queueArray = new int[maxSize];
front = 0;
rear = -1;
numberOfItems = 0; }
//insert an item to queue
public void insert(int i) {
//increment rear and insert item
queueArray[++rear] = i;
nItems++;
}
//remove an item from queue
public int remove() {
//return item and decrement top
int temp = queueArray[front++]; nItems--;
return temp;
}
//view item from top of stack
public void peek() {
return queueArray[front];
}
//check if stack is empty
public void isEmpty() {
return (numberOfItems== -1);
}
//check if stack is full
public void isFull() {
return numberOfItems == maxSize);
}
}
The push() and pop() methods implemented in stacks take constant time to execute. i.e. the time to execute is very quick and is not dependent on the number of items on the stack. In Big O notation this is represented as O(1).
Following are some of the common scenarios in which Stacks can be Used.
- To check if delimiters (parenthesis, brackets etc.) are balanced in a computer program
- To reverse strings
- To traverse the nodes of a binary tree.
- To search the vertices of a graph.
Deques are double-ended queues in which you can insert items either at the front or rear, and can delete items either from the front or rear. Deques provide the methods similar to insertLeft(), insertRight(), removeLeft() and removeRight() to insert and remove from both ends.
A priority queue is a specialized queue in which the items are ordered, so that the lowest (or highest) key is always in the front. So when you get an item from a priority queue then you always get the lowest value item (or highest value item based on how the items are ordered).
Following Java program implements the priority queue functionality. It internally uses an array for the implementation. The array items are ordered in ascending order, and the insert() function inserts an item in the correct position in the array.
class MyPriorityQueue {
private int maxSize;
private int[] queueArray;
private int numberOfItems;
//constructor
public MyPriorityQueue(int maxSize) {
this.maxSize = maxSize;
queueArray = new int[maxSize];
numberOfItems = 0; }
//insert an item to queue
public void insert(int i) {
//increment rear and insert item
if(numberOfItems==0){
queueArray[numberOfItems] = i;
} else {
for(int j=numberOfItems-1; j>=0; j--) {
if(i > queueArray[j]) { queueArray[j+1] = queueArray[j]; } else { break; } } queueArray[++rear] = i;
nItems++;
}
}
//remove an item from queue
public int remove() {
//return item and decrement count
return queueArray[--numberOfItems]; }
//view item from top of stack
public void peek() {
return queueArray[numberOfItems-1];
}
//check if stack is empty
public void isEmpty() {
return (numberOfItems == 0);
}
//check if stack is full
public void isFull() {
return (numberOfItems == maxSize);
}
}