Queue Program in C (Implementation and Examples)

Problem Description

Write a Queue Program in C to implement the queue data structure and display the queue using array and linked list.

What is Queue in C?

The Queue is a linear data structure that follows the FIFO pattern in which the element inserted first at the queue will be removed first.

There are real-world examples of queues, the ticket row for trains, customers waiting in a row, etc.

Here is the FIFO representation of the queue.

Problem Solution

1. To implement the queue we will follow the FIFO principle.
2. We have to keep track of the front and rear pointers of the queue so that we can do the operations enqueue and dequeue.
3. In enqueue operation, we need to keep incrementing the rear while in dequeue the front will be incremented.

Basic Queue Operations:

Enqueue: Elements are added at the end of queue.
Dequeue: Removes the element from the beginning of the queue.
isEmpty(): Check if the queue is empty or not.
isFull(): Check if the queue is full or not.
Peek(): Bring the item to the top of the queue without removing it.

Here, we will implement the queue using two methods:

Implementation of Queue using Array in C

Enqueue Operation
Dequeue Operation

Implementation of Queue using Linked List in C

Enqueue Operation
Dequeue Operation

Method 1: Queue Program in C using Array

In this implementation, we are using a structure in which an array of integers is taken. There are two other variables front and rear which are used to store the array index for dequeue and enqueue respectively.

Initially front and rear have value -1 which means that the queue is empty. On enqueue operation, the rear will be moved by one index forward and the data will be inserted at that index. On dequeue operation, we will store the value at the front index and move the front ahead and then return the stored value.

Let’s see the array implementation of the queue data structure using the C programming language.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Program/Source Code

Here is the array-based implementation of the queue data structure. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C program to implement queues using array

```
 */
```
```
 
```
```
#include<stdio.h>
```
```
 
```
```
#define SIZE 3
```
```
 
```
```
//queue structure 
```
```
struct queue
```
```
{
```
```
    int values[SIZE];
```
```
    int front;
```
```
    int rear;
```
```
};
```
```
 
```
```
void enqueue(int);
```
```
int dequeue();
```
```
int isEmpty();
```
```
int isFull();
```
```
void display();
```
```
 
```
```
//glob
```
```
struct queue q;
```
```
 
```
```
int main()
```
```
{
```
```
    q.front = -1;
```
```
    q.rear = -1;
```
```
    int user_choice, data;
```
```
    char user_active = 'Y';
```
```
 
```

    while (user_active == 'Y' || user_active == 'y')

```
    {
```

        printf("\n--------Queue Program------\n");

```
        printf("\n1. Enqueue");
```
```
        printf("\n2. Dequeue");
```
```
        printf("\n3. Display");
```
```
        printf("\n4. Exit");
```
```
 
```

        printf("\n\nEnter your choice: ");

```
        scanf("%d", &user_choice);
```
```
 
```
```
        switch(user_choice)
```
```
        {
```
```
            case 1:
```

                printf("\nEnter Data: ");

```
                scanf("%d", &data);
```
```
                enqueue(data);
```
```
                break;
```
```
 
```
```
            case 2:
```
```
                if (!isEmpty())
```
```
                {
```
```
                    data = dequeue();
```

                    printf("\n* %d was removed!\n", data);

```
                }
```
```
                else
```
```
                {
```

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

```
                }
```
```
                break;
```
```
 
```
```
            case 3:
```
```
                display();
```
```
                printf("\n");
```
```
                break;
```
```
 
```
```
            case 4:
```

                printf("\n\tProgram was terminated!\n\n");

```
                return 1;
```
```
 
```
```
            default:
```

                printf("\n\tInvalid Choice\n");

```
        }
```
```
 
```

        printf("\nDo You want to continue? ");

```
        fflush(stdin);
```
```
        scanf(" %c", &user_active);
```
```
    }
```
```
    return 0;
```
```
}
```
```
 
```
```
int isEmpty()
```
```
{
```

    if (q.front == -1 || q.front > q.rear)

```
    {
```
```
        return 1;
```
```
    } 
```
```
    return 0;    
```
```
}
```
```
 
```
```
int isFull()
```
```
{
```
```
    if (q.rear == SIZE - 1)
```
```
    {
```
```
        return 1;
```
```
    } 
```
```
    return 0;    
```
```
}
```
```
 
```
```
void enqueue(int data)
```
```
{
```
```
    if (isFull())
```
```
    {
```
```
        printf("\nQueue is Full!\n");
```
```
        return;
```
```
    } 
```
```
    if (isEmpty())
```
```
    {
```
```
        q.front += 1;    
```
```
    } 
```
```
    q.rear += 1;
```
```
    q.values[q.rear] = data;
```

    printf("\n* %d was inserted!\n", data);

```
}
```
```
 
```
```
int dequeue() 
```
```
{
```
```
    if (!isEmpty())
```
```
    {    
```
```
        int data = q.values[q.front];
```
```
        q.front += 1;
```
```
        return data;
```
```
    }
```
```
}
```
```
 
```
```
void display()
```
```
{
```
```
    if (isEmpty())
```
```
    {
```
```
        printf("\nQueue is Empty\n");
```
```
        return;
```
```
    }
```
```
    printf("\n");
```
```
    int begin = q.front;
```
```
    while (begin <= q.rear)
```
```
    {
```
```
        printf("%d ", q.values[begin]);
```
```
        begin += 1;
```
```
    }
```
```
}
```

Program Explanation

Let’s discuss the main functions of the program in detail with examples and their complexities.

enqueue() Function

Enqueue is the operation to insert the new item to the queue from the rear. To perform the enqueue operation, we need to follow the given steps:

Increment the rear by one.
Insert the new item at the rear index of the array.

Example: Insert the new element 23 in the given queue. Here, the size of the queue is 6.

Step 1: Rear is incremented by one, and moved from index 3 to 4.

Step 2: Insert the data at rear

Time Complexity: O(1)
It takes constant time to shift the rear and insert new data into the queue. So, the time complexity of queue program is O(1).

Space Complexity: O(1)
Only temporary space is used for inserting a new node into the queue. So, the space complexity of queue program is O(1).

Run Time Testcases

In this case, we are performing the enqueue operation of queue using array.

--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 34 
 
* 34 was inserted!       
 
Do You want to continue? y
 
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 90
 
* 90 was inserted!       
 
Do You want to continue? y
 
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 12
 
* 12 was inserted!       
 
Do You want to continue? y
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
34 90 12
 
Do You want to continue? n

dequeue() Function

The Dequeue operation is used to remove an item from the front of the queue. To perform the dequeue operation we have to follow the given steps:

Store the value at the front index in a temporary variable called data.
Increment the front by one.
Return the stored value.

Example: Remove an element from the given queue. Here, the front is at index 0 and after performing the dequeue operation, the front will be shifted from index 0 to 1.

Note that the last front value will not be erased after shifting the front.

Step 1: Store the value of front in data

Step 2: Increment the front by one

Time Complexity: O(1)
It takes constant time to shift the front and remove the data from the queue. So, the time complexity is O(1).

Space Complexity: O(1)
Only temporary space is used for inserting a new node into the queue. So, the space complexity is O(1).

Run Time Testcases

In this case, we are performing the dequeue operation of queue using array.

--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
34 90 12
 
Do You want to continue? y
 
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 2
 
* 34 was removed!
 
Do You want to continue? y
 
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
90 12
 
Do You want to continue? y
 
--------Queue Program------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 4
 
        Program was terminated!

Method 2: Queue Program in C using Linked List

In this approach, we will use the concept of the linked list. We have to create the front and rear pointers to keep track of the queue on dequeue and enqueue operations respectively.

The front and rear pointers will be initialized by NULL. The front pointer will point to the first node and the rear pointer will point to the last node of the queue. On enqueue operation, we have to insert a new node at the end of the list while in dequeue, the first node will be removed from the queue.

Let’s see the linked list implementation of the queue using the C programming language.

Program/Source Code

Here is the C program implementation of the queue using a linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C program to implement queue using a linked list

```
 */
```
```
 
```
```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
// structure of a node
```
```
struct node
```
```
{ 
```
```
    int data;
```
```
    struct node* next;
```
```
};
```
```
 
```
```
// globally declared pointers
```
```
struct node* front = NULL;
```
```
struct node* rear = NULL;
```
```
 
```
```
// function prototyping
```
```
void enqueue(int);
```
```
int dequeue();
```
```
void display();
```
```
struct node* create(int);
```
```
int isEmpty();
```
```
 
```
```
int main()
```
```
{
```
```
    int user_choice, data;
```
```
    char user_active = 'Y';
```
```
 
```

    while (user_active == 'Y' || user_active == 'y')

```
    {
```

        printf("\n--------> Queue Program <------\n");

```
        printf("\n1. Enqueue");
```
```
        printf("\n2. Dequeue");
```
```
        printf("\n3. Display");
```
```
        printf("\n4. Exit");
```
```
 
```

        printf("\n\nEnter your choice: ");

```
        scanf("%d", &user_choice);
```
```
 
```
```
        switch(user_choice)
```
```
        {
```
```
            case 1:
```

                printf("\nEnter Data: ");

```
                scanf("%d", &data);
```
```
                enqueue(data);
```
```
                break;
```
```
 
```
```
            case 2:
```
```
                if (!isEmpty())
```
```
                {
```
```
                    data = dequeue();
```

                    printf("\n* %d was removed\n", data);

```
                }
```
```
                else
```
```
                {
```

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

```
                }
```
```
                break;
```
```
 
```
```
            case 3:
```
```
                display();
```
```
                printf("\n");
```
```
                break;
```
```
 
```
```
            case 4:
```

                printf("\n\tProgram was Terminated!\n\n");

```
                return 1;
```
```
 
```
```
            default:
```

                printf("\n\tInvalid Choice\n");

```
        }
```
```
 
```

        printf("\nDo You want to continue? ");

```
        fflush(stdin);
```
```
        scanf(" %c", &user_active);
```
```
    }
```
```
    return 0;
```
```
}
```
```
 
```
```
 
```
```
// creates a new node
```
```
struct node* create(int data)
```
```
{
```

    struct node* new_node = (struct node*) malloc (sizeof(struct node));

```
    if (new_node == NULL)
```
```
    {
```

        printf("\n Memory can't be allocated\n");

```
        return NULL;
```
```
    }
```
```
    new_node->data = data;
```
```
    new_node->next = NULL;
```
```
 
```
```
    return new_node;
```
```
}
```
```
 
```
```
// check if the queue is empty
```
```
int isEmpty()
```
```
{
```
```
    if (front == NULL || rear == NULL)
```
```
    {
```
```
        return 1;
```
```
    }
```
```
    return 0;
```
```
}
```
```
 
```
```
// inserts an item to the queue
```
```
void enqueue(int data)
```
```
{
```

    struct node* new_node = create(data);

```
 
```
```
    if (new_node != NULL)
```
```
    {
```
```
        // if the queue is empty
```
```
        if(front == NULL)
```
```
        {
```
```
            front = new_node;
```
```
        }
```
```
        else
```
```
        {
```
```
            rear->next = new_node;
```
```
        }
```

        // rear pointing to the new node

```
        rear = new_node;
```

        printf("\n* %d was inserted!\n", data);

```
    }
```
```
}
```
```
 
```
```
// removes an item to the queue
```
```
int dequeue()
```
```
{
```
```
    if (!isEmpty())
```
```
    {
```
```
        int data = front->data;
```
```
        front = front->next;
```
```
        return data;
```
```
    }
```
```
}
```
```
 
```
```
// display the queue 
```
```
void display()
```
```
{
```
```
    if (isEmpty())
```
```
    {
```
```
        printf("\nQueue is Empty!\n");
```
```
        return;
```
```
    }
```
```
    printf("\n");
```
```
    struct node* temp = front;
```
```
    while (temp != NULL)
```
```
    {
```
```
        printf("%d ", temp->data);
```
```
        temp = temp->next;
```
```
    }
```
```
}
```

Program Explanation

Let’s discuss the main functions of the program in detail with examples and their complexities.

enqueue() Function

To perform the enqueue operation, we have to follow the given steps:

Update the next pointer of the rear node to the new node.
Update the rear pointer to the new node.

Example: Insert the new node with data 77 at the end of the given queue.

Step 1: Updating the next of the rear node to the new node.

Step 2: Update the rear pointer to the new node.

Time Complexity: O(1)
Updating the rear pointer does take a constant amount of time. So, the time complexity is O(1).

Space Complexity: O(1)
Since using the temporary variables to perform the enqueue operation so space is constant. So, the space complexity is O(1).

Run Time Testcases

In this case, we are performing the dequeue operation of queue using array.

--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 90
 
* 90 was inserted!       
 
Do You want to continue? y
 
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 56
 
* 56 was inserted!       
 
Do You want to continue? y
 
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 1
 
Enter Data: 12
 
* 12 was inserted!       
 
Do You want to continue? y
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
90 56 12
 
Do You want to continue? n

dequeue() Function

To perform the dequeue operation we have to follow the given steps:

Store the value at the front node.
Move the front node to its next node.

Example: Let’s see an example of the dequeue operation in the given queue.

Step 1: Store the data of the front node.

Step 2: Move the front pointer to next node.

Time Complexity: O(1)
Updating the front pointer does take a constant amount of time. So, the time complexity is O(1).

Space Complexity: O(1)
Since using the temporary variables to perform the dequeue operation, space is constant i.e. O(1).

Run Time Testcases

In this case, we are performing the dequeue operation of queue using linked list.

--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
90 56 12
 
Do You want to continue? y
 
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 2
 
* 90 was removed
 
Do You want to continue? y
 
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 3
 
56 12
 
Do You want to continue? y
 
--------> Queue Program <------
 
1. Enqueue
2. Dequeue
3. Display
4. Exit
 
Enter your choice: 4
 
        Program was Terminated!

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

« Prev - C Program to Implement Stack

» Next - Graph Representation using Linked List in C

Related Posts:

Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Computer Science MCQs
Check Data Structure Books

Recommended Articles: