Creating a Queue in C

A queue in C is basically a linear data structure to store and manipulate the data elements. It follows the order of First In First Out (FIFO).

In queues, the first element entered into the array is the first element to be removed from the array.

For example, let’s consider the scenario of a bus-ticket booking stall. Here, the fashion of a C programming queue is followed. The tickets are distributed on the first-come-first-serve basis i.e. the first one to enter is the first one to be served with the tickets.

A queue is open at both ends. One end is provided for the insertion of data and the other end for the deletion of data.

A queue can be implemented with any programming language such as C, Java, Python, etc.

Operations Associated with a Queue in C

A queue being an Abstract Data Structure provides the following operations for manipulation on the data elements:

• isEmpty(): To check if the queue is empty
• isFull(): To check whether the queue is full or not
• dequeue(): Removes the element from the frontal side of the queue
• enqueue(): It inserts elements to the end of the queue
• Front: Pointer element responsible for fetching the first element from the queue
• Rear: Pointer element responsible for fetching the last element from the queue

Working of Queue Data Structure

Queue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.

• Front and Rear pointers keep the record of the first and last element in the queue.
• At first, we need to initialize the queue by setting Front = -1 and Rear = -1
• In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we’ll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
• In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we’ll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have to set the values of the Front and Rear index to -1.

Implementation of Queue in C

Queues in C can be implemented using Arrays, Lists, Structures, etc. Below here we have implemented queues using Arrays in C.

Example:

#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
    int ch;
    while (1)
    {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
            enqueue();
            break;
            case 2:
            dequeue();
            break;
            case 3:
            show();
            break;
            case 4:
            exit(0);
            default:
            printf("Incorrect choice \n");
        } 
    } 
} 
 
void enqueue()
{
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Overflow \n");
    else
    {
        if (Front == - 1)
      
        Front = 0;
        printf("Element to be inserted in the Queue\n : ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
} 
 
void dequeue()
{
    if (Front == - 1 || Front > Rear)
    {
        printf("Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
} 
 
void show()
{
    
    if (Front == - 1)
        printf("Empty Queue \n");
    else
    {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", inp_arr[i]);
        printf("\n");
    }
} 

Output:

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue: 
10 20 

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue: 
20 

Implementation of Queue using Stacks

Stack Data Structure can be used to implement the operations of the queue. We’ll need two stacks to implement a queue using them. Before you work through the examples below, make sure you understand the functioning of stacks very well.

A queue can be implemented using Stacks by either of the following ways:

• Making the enqueue operation costly
• Making the dequeue operation costly

Method 1: Making the enqueue Operation Costly

Let us assume two stacks: S1 and S2 to implement queue operations using the same.

• If S1 is not empty, push all elements to stack 2 (S2)
• In order to perform the enqueue operation, we will assume ‘x’ to be the element to be entered into the queue. We will push ‘x’ back to Stack S1 so it comes up on the top.
• Further, push all the elements of stack S2 back to Stack S1

Note: The time complexity of the enqueue operation would be O(n).

• In order to perform dequeue operation, we’ll need to pop an item from the Stack S1 since now the first inserted element is on the top in S1 instead of being at the bottom.

Note: The time complexity of the dequeue operation would be O(1).

If you analyze the time complexities of the Enqueue and Dequeue operations using Stack, you’ll find out that the Enqueue operation is much costlier than the Dequeue operation.

Thus, as mentioned above, we make the first entered or the oldest entered element to remain at the top of Stack S1 so that it gets removed when the Dequeue operation is invoked.

Method 2: Making the Dequeue operation costly

Let us again assume two Stacks: S1 and S2 to implement queue operations using the same.

• In order to implement enqueue operation, we insert the newly entered element at the top of Stack S1. Thus, the time complexity of the Enqueue operation using Stacks becomes O(1).
• For the implementation of dequeue operation, it checks for the Underflow condition of Stack S1 and S2. If both the Stacks stands out to be empty, an error would be raised.
• If the Stack S2 is empty and S1 is not empty, then all the elements from Stack S1 are moved to Stack S2 and the top element of Stack S2 is popped out and returned out of the Dequeue operation.
• Thus, the time complexity of the dequeue operation using Stacks becomes O(n).

Applications of Queue Data Structure

• CPU Scheduling
• Disk Scheduling
• Asynchronous data transfer between processors such as File IO, etc.
• Breadth-First Search Algorithm (BFS)

Conclusion

In this article, we have understood the working of queue data structure and have also shadowed over the implementation of queues using stack data structure.

References

• Queue in C
• Queue using Stacks