What is Queue?
A queue is a linear list of elements in which deletions can take place only at one end called the front, and insertions can take place only at the end called the rear. The queue is a First In First Out type of data structure (FIFO), the terms FRONT and REAR are used in describing a linear list only when it is implemented as a queue.
In computer science queues are used in multiple places e.g. in a time-sharing system program with the same priority from a queue waiting to be executed. A queue is a non-primitive linear data structure. it is a homogeneous collection of elements.
The process to add an element into a queue is called Enqueue and the process of removal of an element from the queue is called Dequeue.
Basic features of Queue
- Like stack, queue is also an ordered list of elements of similar data types.
- Queue is a FIFO( First in First Out ) structure.
- Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
- peek() function is used to return the value of first element without dequeuing it.
Implementation of Queue Data Structure
The queue can be implemented in two ways :
- Static implementation (using arrays)
- Dynamic implementation (using linked list)
Basics operations on the stack
- Enqueue
- Dequeue
Enqueue operation:
Algorithm for INSERTION operation
- Check for the overflow condition.
- Check if the queue is empty.
- If the queue is empty, then both FRONT and REAR are set to zero, so that the new value can be stored at the 0th location. Otherwise, if the queue already has some values, then REAR is incremented so that it points to the next location in the array.
- The value is stored in the queue at the location pointed by REAR.
Queue_Insert (Queue, Size, Front, Rear, x)
{
if (Rear == Size - 1)
Print Over flow
if (Front = = -1)
Set Front = 0 && Rear = 0
Else
Rear = R + 1
Queue[Rear] = x
EXIT
}
Dequeue operation:
Algorithm for DELETION operation
- Check for underflow condition. An underflow occurs if FRONT = –1 or FRONT > REAR.
- If queue has some values, then FRONT is incremented so that it now points to the next value in the queue.
Queue_DELETE (Queue, Size, Front, Rear)
{
if (Front == - 1)
Print Under flow
x = Queue [Front]
if (Front = = Rear)
Set Front = -1 && Rear = -1
Else
Front = Front + 1
EXIT
}
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Queue {
int front, rear, capacity;
int* queue;
public:
Queue(int val)
{
front = rear = 0;
capacity = val;
queue = new int;
}
Queue() { delete[] queue; }
void queueEnqueue(int data)
{
if (capacity == rear) {
cout<<"Queue is full";
return;
}
else {
queue[rear] = data;
rear++;
}
return;
}
void queueDequeue()
{
if (front == rear) {
cout<<"Queue is empty"<<endl;
return;
}
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
rear--;
}
return;
}
void queueDisplay()
{
int i;
if (front == rear) {
cout<<("Queue is Empty");
return;
}
cout<<endl;
for (i = front; i < rear; i++) {
cout<<queue[i]<<endl;
}
return;
}
void queueFront()
{
if (front == rear) {
cout<<"Queue is Empty";
return;
}
cout<<"Front Element is: "<<queue[front];
return;
}
};
int main()
{
Queue q(4);
q.queueDisplay();
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
q.queueDisplay();
q.queueEnqueue(60);
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
printf("after two node deletion");
q.queueDisplay();
q.queueFront();
return 0;
}
Output:
Queue is Empty
20
30
40
50
Queue is full
20
30
40
50
after two node deletion
40
50
Front Element is: 40
Java Code
import java.util.*;
class Queue {
private static int front, rear, capacity;
private static int queue[];
Queue(int val)
{
front = rear = 0;
capacity = val;
queue = new int[capacity];
}
static void queueEnqueue(int data)
{
if (capacity == rear) {
System.out.println("Queue is full");
return;
}
else {
queue[rear] = data;
rear++;
}
return;
}
static void queueDequeue()
{
if (front == rear) {
System.out.println("Queue is empty");
return;
}
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
if (rear < capacity)
queue[rear] = 0;
rear--;
}
return;
}
static void queueDisplay()
{
int i;
if (front == rear) {
System.out.println("Queue is Empty");
return;
}
for (i = front; i < rear; i++) {
System.out.printf("%d ", queue[i]);
}
System.out.println();
return;
}
static void queueFront()
{
if (front == rear) {
System.out.println("Queue is Empty");
return;
}
System.out.print("Front Element is: "+queue[front]);
return;
}
}
public class StaticQueueinjava {
public static void main(String[] args)
{
Queue q = new Queue(4);
q.queueDisplay();
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
q.queueDisplay();
q.queueEnqueue(60);
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
System.out.println("after two node deletion");
q.queueDisplay();
q.queueFront();
}
}
Output:
Queue is Empty
20 30 40 50
Queue is full
20 30 40 50
after two node deletion
40 50
Front Element is: 40
Complexity Analysis of Queue Operations
Just like Stack, in the case of a Queue too, we know exactly, on which position a new element will be added and from where an element will be removed, hence both these operations require a single step.
- Enqueue: O(1)
- Dequeue: O(1)
- Size: O(1)
Special thanks to Swarnavo Mondal for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article