Queue in C – Data Structures Part 4

This article is a continuation of the  Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our previous article, we have seen how to implement the stack data structure using the Linked List. In this article, we will see Queue in C Programming – Data Structures Part 4.

Queue in C Programming

What is Queue in general?

In real life, a Queue is a line or sequence of people or vehicles or any objects awaiting their turn to be attended to or to proceed. Let’s consider the below real-time examples.

  • A queue of people waiting for their turn to come to take money from the ATM machine,
  • A queue of vehicles waiting for the traffic signal to turn green,
  • A queue of people waiting to buy tickets in a railway station or movie theater.
  • etc.
Photo by – 4GIFS.com

Gif Image

The above gif image explains a funny scenario that everyone faced even one time in our life. Okay, let’s start our original topic.

What is Queue in C programming language?

A queue is a linear data structure that follows the FIFO (First In First Out) principle in deletion and insertion operations. That means the item that was inserted first should be removed first.

Unlike a stack, a queue is open at both ends called as Rear and Front. One end is provided for the insertion of the data and the other end is for the deletion of the data.

Refer to the below image.

Types of Queues

There are four different types of queues:

  • Simple Queue
  • Circular Queue
  • Priority Queue
  • Double Ended Queue

Note: In this post, we will focus on the simple queue and its implementation.

Ways to implement the Queue

There are two ways of implementing the Queue:

In this article, we will be implementing the queue using an array.

We will have to maintain two pointers that are used to track the FRONT and REAR ends.

FRONT is used to track the first element of the queue. REAR is used to track the last element of the queue. Initially, set the value of FRONT and REAR to -1.

Operations on Queue

A queue allows the following operations:

We will see them one by one.

Enqueue

This method is used to add the element to the queue. As we have two ends (Front end, Rear end) in the queue, this addition will happen at the Rear end.

  1. First, check whether the Queue is Full or not.
  2. If it is full, then we cannot add a new element to it. This is overflow. So exit.
  3. If it is not full, and if this is the very first element, make the FRONT to 0.
  4. The increase the REAR index by 1.
  5. Finally, add the new element in the position pointed to by REAR.

The below flow chart may help you to understand the logic.

Enqueue in C

Example

void enQueue()
{
  if( isFull() == true )
  {
    printf("ERROR: Queue is Overflow!!!\n");
  }
  else
  {
    if( FRONT == -1 )
    {
      FRONT = 0;  
    }
    
    REAR++;
    
    int value;
    printf("Enter a value to be add: ");
    scanf("%d",&value);
    queue[REAR] = value;
    printf("%d is added to the Queue\n", value);
  }
}

Dequeue

This method is used to remove the element from the queue. As we have two ends (Front end, Rear end) in the queue, this removal will happen at the Front end.

  1. First, check whether the Queue is empty or not.
  2. If that is empty, we cannot remove the element as no elements are present. So exit from there.
  3. If it is not empty, then return the value which is pointing to FRONT.
  4. Increment the FRONT.

The below flow chart may help you to understand the logic.

Dequeue in C

Example

void deQueue()
{
  if( isEmpty() == true )
  {
    printf("ERROR: Queue is Underflow!!!\n");
  }
  else
  {
    printf("%d is deleted\r\n", queue[FRONT]);
    
    FRONT++;
    
    /* Reset it, if we reached the end */
    if(FRONT > REAR)
    {
      FRONT = REAR = -1;
    }
  }
}

IsEmpty

This is used to check whether the queue is empty or not.

bool isEmpty()
{
  bool isQueueEmpty = false;
  
  if( FRONT == -1 )
  {
    isQueueEmpty = true;
  }

  return (isQueueEmpty);
}

IsFull

This is used to check whether the queue is full or not.

bool isFull()
{
  bool isQueueFull = false;
  
  if( REAR == MAX-1 )
  {
    isQueueFull = true;
  }
  
  return (isQueueFull);
}

Peek

This function is used to see the element in the front of the queue. This operation will not remove the element.

void peek()
{
  if( isEmpty() == true )
  {
    printf("Queue is Empty!!!\n");
  }
  else 
  {
    printf("Top Element is %d\n", queue[FRONT]);
  }
}

Implementation of the queue in C using an array

Before writing a code, you should keep the below points in your mind.

  • A pointer called FRONT and REAR is used to keep track of the first and last element in the queue. So, initialize it with -1. If the value of the FRONT is -1, then the queue is empty. If the value of the REAR is equal to MAX-1, then the queue is full.
  • Whenever you enqueue the element to the queue, you have to check whether the queue is full or not. If it is full, then you should not add the elements as the queue will overflow. If it is not full, then add the element.
  • When you want to dequeue the element from the queue, you have to check whether the queue is empty or not. If it is empty, you should not remove the element as the queue is an underflow. You can remove it if the queue is not empty.

Source Code (Queue in C program)

#include<stdio.h>
#include<stdbool.h>

#define MAX 3       // Queue's maximum size

//Function declaration
void enQueue(void);
void deQueue(void);
bool isEmpty(void);
void display(void);
bool isFull(void);
void peek(void);

int queue[MAX];
int REAR  = -1;
int FRONT = -1;

int main()
{
  int choice;
  printf("*** Queue  Implementation using Array***");
  
  while(1)
  {
    printf("\n1. Enqueue\n");
    printf("2. Dequeue\n");
    printf("3. Display all the Elements\n");
    printf("4. Peek Top element\n");
    printf("Enter the Choice: ");
    scanf("%d",&choice);
    
    switch(choice)
    {
      case 1:
      {
        //Inserting the element into the queue
        enQueue();  
        break;
      }
      case 2:
      {
        //Removing the element from the queue
        deQueue();
        break;
      }
      case 3:
      {
        //Displaying all the elements in the queue
        display();
        break;
      }
      case 4:
      {
        //Displaying the element which is in the front of the queue
        peek();
        break;
      }
      default:
      {
        printf ("\nPlease Enter a Valid Choice: ");
        break;
      }
    }
  }
}

bool isFull()
{
  bool isQueueFull = false;
  
  if( REAR == MAX-1 )
  {
    isQueueFull = true;
  }
  
  return (isQueueFull);
}

bool isEmpty()
{
  bool isQueueEmpty = false;
  
  if( FRONT == -1 )
  {
    isQueueEmpty = true;
  }
  
  return (isQueueEmpty);
}
    
void enQueue()
{
  if( isFull() == true )
  {
    printf("ERROR: Queue is Overflow!!!\n");
  }
  else
  {
    if( FRONT == -1 )
    {
      FRONT = 0;  
    }
    
    REAR++;
    
    int value;
    printf("Enter a value to be add: ");
    scanf("%d",&value);
    queue[REAR] = value;
    printf("%d is added to the Queue\n", value);
  }
}

void deQueue()
{
  if( isEmpty() == true )
  {
    printf("ERROR: Queue is Underflow!!!\n");
  }
  else
  {
    printf("%d is deleted\r\n", queue[FRONT]);
    
    FRONT++;
    /* Reset it, if we reached the end */
    if (FRONT > REAR)
    {
      FRONT = REAR = -1;
    }
  }
}

void display()
{
  if( isEmpty() == true )
  {
    printf("Queue is Empty!!!\n");
  }
  else 
  {
    int i;
    printf("Queue elements are:\n");
    for (i = FRONT; i <= REAR; i++)
    {
      printf("%d  ", queue[i]);
    }
    printf("\n");
  }
}

void peek()
{
  if( isEmpty() == true )
  {
    printf("Queue is Empty!!!\n");
  }
  else 
  {
    printf("Top Element is %d\n", queue[FRONT]);
  }
}

Output

*** Queue  Implementation using Array***
1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 3
Queue is Empty!!!

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be add: 10
10 is added to the Queue

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be add: 20
20 is added to the Queue

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be add: 30
30 is added to the Queue

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 1
ERROR: Queue is Overflow!!!

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 3
Queue elements are:
10  20  30  

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 2
10 is deleted


1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 2
20 is deleted


1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 2
30 is deleted


1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be add: 15
15 is added to the Queue

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 4
Top Element is 15

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice: 3
Queue elements are:
15  

1. Enqueue
2. Dequeue
3. Display all the Elements
4. Peek Top element
Enter the Choice:

Drawback of array implementation

  • The main problem is Limited memory. You cannot change the size of the queue while running(dynamically).
  • Unfilled space will not be utilized as the front pointer of the queue would have moved ahead. This has been explained in the next section.

Limitations of Queue

If you take the above method, let’s assume the queue is full. It is having data of 10, 20, and 30 like below.

Now, you are doing two dequeue operations. So, the FRONT and REAR will be pointing to the last element. Now the queue looks like below.

implementation of queue in c

Now two elements are free. If you try to add any new element, it will throw you an overflow. Yes, We have the free space. But, those spaces can’t be used as we can’t traverse them again. If you dequeue 30, then the FRONT and REAR will be reset to -1. Now you can able to add a new element. We can rectify this problem by using the Circular Queue.

The complexity of the Queue

The complexity of enqueue and dequeue operations in a queue using an array is O(1).

Applications of Queue

  1. Breadth-first search (BFS) algorithm.
  2. It is used to handle interrupts in real-time systems.
  3. Job Scheduling, to maintain a queue of processes in operating systems (FIFO order).
  4. The queue of packets in data communication.
  5. CPU scheduling, Disk Scheduling.
  6. When data is transferred asynchronously between two processes, the queue is used for synchronization. For example IO Buffers, pipes, file IO, etc.
  7. Call Center phone systems use Queues to hold people calling them in order.
  8. Handling website traffic.
  9. Routers and switches in networking.
  10. Maintaining the playlist in media players.

In our next tutorial, we will implement a Queue data structure using a Linked List in C programming.

You can also read the below topics.

Linux Device Driver TutorialsC Programming Tutorials
FreeRTOS TutorialsNuttX RTOS Tutorials
RTX RTOS TutorialsInterrupts Basics
I2C Protocol – Part 1 (Basics)I2C Protocol – Part 2 (Advanced Topics)
STM32 TutorialsLPC2148 (ARM7) Tutorials
PIC16F877A Tutorials8051 Tutorials
Unit Testing in C TutorialsESP32-IDF Tutorials
Raspberry Pi TutorialsEmbedded Interview Topics
Reset Sequence in ARM Cortex-M4BLE Basics
VIC and NVIC in ARMSPI – Serial Peripheral Interface Protocol
STM32F7 Bootloader TutorialsRaspberry PI Pico Tutorials
STM32F103 Bootloader TutorialsRT-Thread RTOS Tutorials
Zephyr RTOS Tutorials – STM32Zephyr RTOS Tutorials – ESP32
AUTOSAR TutorialsUDS Protocol Tutorials
Product ReviewsSTM32 MikroC Bootloader Tutorial
VHDL Tutorials

Credits:

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Table of Contents