top of page
Writer's picturePushp Raj

Introduction to Queue – Data Structure and Algorithm Tutorials

Updated: Jan 23



Queues are data structures and algorithms used to store and process data in a particular order. This follows the FIFO (first in, first out) principle. That is, the first item entered is processed first. Queues are commonly used by applications such as operating systems, network protocols, and web servers to manage requests from multiple users or tasks. It also helps ensure system fairness by granting equal access to all users or tasks. Queue data structures can be implemented using various algorithms such as linked lists, arrays, and circular arrays.


Learn the concepts of DSA with the complete beginner-friendly video tutorial course Data Structures & Algorithms using Java


Representation of Queues



Complexity



Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:

  • Enqueue : Add an element to the end of the queue

  • Dequeue : Remove an element from the front of the queue

  • IsEmpty : Check if the queue is empty

  • IsFull : Check if the queue is full

  • Peek : Get the value of the front of the queue without removing it


Types of Queue


  • Simple Queue or Linear Queue

  • Circular Queue

  • Priority Queue

  • Double Ended Queue (or Deque)


Linear Queue

A linear queue is a data structure used to store and manage data on a first-in, first-out (FIFO) basis. It is a sort of abstract data type consisting of an ordered collection of elements, with the addition of new elements and the removal of existing elements at one end, called the "front". A circular queue that allows both additions and deletions at both ends. Linear queues are useful for implementing batches and solving problems related to task or process scheduling. It can also be used to store data in sequence, making it ideal for applications such as job scheduling and task management systems.





Ways to implement the queue


Using Array –

Arrays can be used to represent queue data structures. In this representation, the queue is implemented using a fixed-size array, with two pointers (front and back) to track the first and last element of the queue respectively.


Initially, both front and back are set to -1 to indicate that the queue is empty. When an item is added to the queue, the rear pointer is incremented and the item is inserted at the index pointed to by the rear. If the queue is empty, the front and back are incremented and the first element is inserted at index 0. When an element is dequeued, the front pointer is incremented and the element at the index pointed to by the front is returned. Both front and back are set to -1 when the queue is empty.


Using Linked List –

Linked lists can also be used to represent queue data structures. In this representation, the queue is implemented using a singly linked list where each node stores an element of the queue and a pointer to the next node.


Two pointers, front and back, are used to track the first and last element of the queue respectively. Initially, both front and back are set to NULL to indicate that the queue is empty.


When an item is added to the queue, a new node is created and the item is stored in the node. If the queue is empty, both the front and back are set to point to the new node. Otherwise, the back pointer is updated to point to the new node.


As the element is dequeued, the front pointer is updated to point to the next node, and the element stored at the node pointed to by the original front pointer is returned. Both front and back are set to NULL when the queue is empty.


Implementation of Queue in C


// Queue implementation in C


#include <stdio.h>

#define SIZE 5


void enQueue(int);

void deQueue();

void display();


int items[SIZE], front = -1, rear = -1;


int main() {

//deQueue is not possible on empty queue

deQueue();


//enQueue 5 elements

enQueue(1);

enQueue(2);

enQueue(3);

enQueue(4);

enQueue(5);


// 6th element can't be added to because the queue is full

enQueue(6);


display();


//deQueue removes element entered first i.e. 1

deQueue();

//Now we have just 4 elements

display();

return 0;

}


void enQueue(int value) {

if (rear == SIZE - 1)

printf("\nQueue is Full!!");

else {

if (front == -1)

front = 0;

rear++;

items[rear] = value;

printf("\nInserted -> %d", value);

}

}


void deQueue() {

if (front == -1)

printf("\nQueue is Empty!!");

else {

printf("\nDeleted : %d", items[front]);

front++;

if (front > rear)

front = rear = -1;

}

}


// Function to print the queue

void display() {

if (rear == -1)

printf("\nQueue is Empty!!!");

else {

int i;

printf("\nQueue elements are:\n");

for (i = front; i <= rear; i++)

printf("%d ", items[i]);

}

printf("\n");

}



Circular Queue

A circular queue is a data structure used to store and retrieve data in computer programming. This is a linear data structure that stores elements cyclically. It works on the principle of FIFO (first in, first out). In other words, items added to the queue first are removed from the queue first.


Working of Circular Queue

A circular queue is a data structure that uses arrays to store elements in a circular fashion. Used to store and manage data in a queue-like manner, where the last element of the queue is wrapped to become the first element. This allows for efficient memory usage and efficient insert and deletes operations. A circular queue works by maintaining two-pointers. One point to the head of the queue and one point to the back of the queue. When an item is added to the queue it is inserted at the back pointer position, but when an item is removed from the queue it is removed from the front pointer position. This ensures that items are always added and removed on a first-in, first-out (FIFO) basis.


Operations on Circular Queue

  • Front: It is used to get the front element from the Queue.

  • Rear: It is used to get the rear element from the Queue.

  • enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.

  • deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.


Implementation of Circular Queue in C

// Circular Queue implementation in C


#include <stdio.h>

#define SIZE 5


int items[SIZE];

int front = -1, rear = -1;


// Check if the queue is full

int isFull() {

if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;

return 0;

}


// Check if the queue is empty

int isEmpty() {

if (front == -1) return 1;

return 0;

}


// Adding an element

void enQueue(int element) {

if (isFull())

printf("\n Queue is full!! \n");

else {

if (front == -1) front = 0;

rear = (rear + 1) % SIZE;

items[rear] = element;

printf("\n Inserted -> %d", element);

}

}


// Removing an element

int deQueue() {

int element;

if (isEmpty()) {

printf("\n Queue is empty !! \n");

return (-1);

} else {

element = items[front];

if (front == rear) {

front = -1;

rear = -1;

}

// Q has only one element, so we reset the

// queue after dequeing it. ?

else {

front = (front + 1) % SIZE;

}

printf("\n Deleted element -> %d \n", element);

return (element);

}

}


// Display the queue

void display() {

int i;

if (isEmpty())

printf(" \n Empty Queue\n");

else {

printf("\n Front -> %d ", front);

printf("\n Items -> ");

for (i = front; i != rear; i = (i + 1) % SIZE) {

printf("%d ", items[i]);

}

printf("%d ", items[i]);

printf("\n Rear -> %d \n", rear);

}

}


int main() {

// Fails because front = -1

deQueue();


enQueue(1);

enQueue(2);

enQueue(3);

enQueue(4);

enQueue(5);


// Fails to enqueue because front == 0 && rear == SIZE - 1

enQueue(6);


display();

deQueue();


display();


enQueue(7);

display();


// Fails to enqueue because front == rear + 1

enQueue(8);


return 0;

}


72 views

Related Posts

See All

Comments


Subscribe to Our Newsletter

Thanks for submitting!

bottom of page