Queue
Queue, like Stack, is also an abstract data structure. The thing that makes queue different from
stack is that a queue is open at both its ends. Hence, it follows FIFO (First-In-First-Out) structure,
i.e. the data item inserted first will also be accessed first. The data is inserted into the queue through
one end and deleted from it using the other end.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.
Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or
pointers. As a small example in this tutorial, we implement queues using a one-dimensional array.
Basic Operations
Queue operations also include initialization of a queue, usage and permanently deleting the data
from the memory.
The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(),
isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check
the status of the queue.
Queue uses two pointers − front and rear. The front pointer accesses the data from the front end
(helping in enqueueing) while the rear pointer accesses data from the rear end (helping in
dequeuing).
Insertion operation: enqueue()
The enqueue() is a data manipulation operation that is used to insert elements into the stack. The
following algorithm describes the enqueue() operation in a simpler way.
Algorithm
1 − START
2 – Check if the queue is full.
3 − If the queue is full, produce overflow error and exit.
4 − If the queue is not full, increment rear pointer to point the next empty space.
5 − Add data element to the queue location, where the rear is pointing.
6 − return success.
7 – END
Example
Following are the implementations of this operation in various programming languages −
import [Link];
import [Link];
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
[Link](6);
[Link](1);
[Link](8);
[Link](4);
[Link](7);
[Link]("The queue is: " + q);
}
}
Output
The queue is: [6, 1, 8, 4, 7]
Deletion Operation: dequeue()
The dequeue() is a data manipulation operation that is used to remove elements from the stack.
The following algorithm describes the dequeue() operation in a simpler way.
Algorithm
1 – START
2 − Check if the queue is empty.
3 − If the queue is empty, produce underflow error and exit.
4 − If the queue is not empty, access the data where front is pointing.
5 − Increment front pointer to point to the next available data element.
6 − Return success.
7 – END
Example
Following are the implementations of this operation in various programming languages −
import [Link];
import [Link];
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
[Link](6);
[Link](1);
[Link](8);
[Link](4);
[Link](7);
[Link]("The queue is: " + q);
int n = [Link]();
[Link]("The element deleted is: " + n);
[Link]("Queue after deletion: " + q);
}
}
Output
The queue is: [6, 1, 8, 4, 7]
The element deleted is: 6
Queue after deletion: [1, 8, 4, 7]
The peek() Operation
The peek() is an operation which is used to retrieve the frontmost element in the queue, without
deleting it. This operation is used to check the status of the queue with the help of the pointer.
Algorithm
1 – START
2 – Return the element at the front of the queue
3 – END
Example
Following are the implementations of this operation in various programming languages −
import [Link];
import [Link];
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
[Link](6);
[Link](1);
[Link](8);
[Link](4);
[Link](7);
[Link]("The queue is: " + q);
}
}
Output
The queue is: [6, 1, 8, 4, 7]
The isFull() Operation
The isFull() operation verifies whether the stack is full.
Algorithm
1 – START
2 – If the count of queue elements equals the queue size, return true
3 – Otherwise, return false
4 – END
Example
Following are the implementations of this operation in various programming languages −
import [Link].*;
public class QueueExample {
private int intArray[];
private int front;
private int rear;
private int itemCount;
private int MAX;
QueueExample(int size) {
intArray = new int[size];
front = 0;
rear = -1;
MAX = size;
itemCount = 0;
}
public boolean isFull() {
return itemCount == MAX;
}
public void insert(int key) {
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = key;
itemCount++;
}
}
public static void main (String[] args) {
QueueExample q = new QueueExample(5);
[Link](1); // inserting 1 in the stack
[Link](2);
[Link](3);
[Link](4);
[Link](5);
[Link]("Stack Full? " + [Link]());
}
}
Output
Stack Full? true
The isEmpty() operation
The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.
Algorithm
1 – START
2 – If the count of queue elements equals zero, return true
3 – Otherwise, return false
4 – END
Example
Following are the implementations of this operation in various programming languages −
import [Link].*;
public class QueueExample {
private int intArray[];
private int front;
private int rear;
private int itemCount;
private int MAX;
QueueExample(int size) {
intArray = new int[size];
front = 0;
rear = -1;
MAX = size;
itemCount = 0;
}
public boolean isEmpty() {
return itemCount == 0;
}
public static void main (String[] args) {
QueueExample q = new QueueExample(5);
[Link]("Stack Empty? " + [Link]());
}
}
Output
Stack Empty? true