Queue Program in C

«
»
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.
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:

advertisement
advertisement

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.

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.

  1. /*
  2.  * C program to implement queues using array
  3.  */
  4.  
  5. #include<stdio.h>
  6.  
  7. #define SIZE 3
  8.  
  9. //queue structure 
  10. struct queue
  11. {
  12.     int values[SIZE];
  13.     int front;
  14.     int rear;
  15. };
  16.  
  17. void enqueue(int);
  18. int dequeue();
  19. int isEmpty();
  20. int isFull();
  21. void display();
  22.  
  23. //glob
  24. struct queue q;
  25.  
  26. int main()
  27. {
  28.     q.front = -1;
  29.     q.rear = -1;
  30.     int user_choice, data;
  31.     char user_active = 'Y';
  32.  
  33.     while (user_active == 'Y' || user_active == 'y')
  34.     {
  35.         printf("\n--------Queue Program------\n");
  36.         printf("\n1. Enqueue");
  37.         printf("\n2. Dequeue");
  38.         printf("\n3. Display");
  39.         printf("\n4. Exit");
  40.  
  41.         printf("\n\nEnter your choice: ");
  42.         scanf("%d", &user_choice);
  43.  
  44.         switch(user_choice)
  45.         {
  46.             case 1:
  47.                 printf("\nEnter Data: ");
  48.                 scanf("%d", &data);
  49.                 enqueue(data);
  50.                 break;
  51.  
  52.             case 2:
  53.                 if (!isEmpty())
  54.                 {
  55.                     data = dequeue();
  56.                     printf("\n* %d was removed!\n", data);
  57.                 }
  58.                 else
  59.                 {
  60.                     printf("\nQueue is Empty!\n");
  61.                 }
  62.                 break;
  63.  
  64.             case 3:
  65.                 display();
  66.                 printf("\n");
  67.                 break;
  68.  
  69.             case 4:
  70.                 printf("\n\tProgram was terminated!\n\n");
  71.                 return 1;
  72.  
  73.             default:
  74.                 printf("\n\tInvalid Choice\n");
  75.         }
  76.  
  77.         printf("\nDo You want to continue? ");
  78.         fflush(stdin);
  79.         scanf(" %c", &user_active);
  80.     }
  81.     return 0;
  82. }
  83.  
  84. int isEmpty()
  85. {
  86.     if (q.front == -1 || q.front > q.rear)
  87.     {
  88.         return 1;
  89.     } 
  90.     return 0;    
  91. }
  92.  
  93. int isFull()
  94. {
  95.     if (q.rear == SIZE - 1)
  96.     {
  97.         return 1;
  98.     } 
  99.     return 0;    
  100. }
  101.  
  102. void enqueue(int data)
  103. {
  104.     if (isFull())
  105.     {
  106.         printf("\nQueue is Full!\n");
  107.         return;
  108.     } 
  109.     if (isEmpty())
  110.     {
  111.         q.front += 1;    
  112.     } 
  113.     q.rear += 1;
  114.     q.values[q.rear] = data;
  115.     printf("\n* %d was inserted!\n", data);
  116. }
  117.  
  118. int dequeue() 
  119. {
  120.     if (!isEmpty())
  121.     {    
  122.         int data = q.values[q.front];
  123.         q.front += 1;
  124.         return data;
  125.     }
  126. }
  127.  
  128. void display()
  129. {
  130.     if (isEmpty())
  131.     {
  132.         printf("\nQueue is Empty\n");
  133.         return;
  134.     }
  135.     printf("\n");
  136.     int begin = q.front;
  137.     while (begin <= q.rear)
  138.     {
  139.         printf("%d ", q.values[begin]);
  140.         begin += 1;
  141.     }
  142. }
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:

advertisement
  1. Increment the rear by one.
  2. 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.

Array Implementation of the Queue - enqueue() Function

Step 2: Insert the data at rear

Array Implementation of the Queue - enqueue() Function

advertisement

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:

  1. Store the value at the front index in a temporary variable called data.
  2. Increment the front by one.
  3. 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

Array Implementation of the Queue - dequeue() Function

Step 2: Increment the front by one

Array Implementation of the Queue - dequeue() Function

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.

  1. /*
  2.  * C program to implement queue using a linked list
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7.  
  8. // structure of a node
  9. struct node
  10. { 
  11.     int data;
  12.     struct node* next;
  13. };
  14.  
  15. // globally declared pointers
  16. struct node* front = NULL;
  17. struct node* rear = NULL;
  18.  
  19. // function prototyping
  20. void enqueue(int);
  21. int dequeue();
  22. void display();
  23. struct node* create(int);
  24. int isEmpty();
  25.  
  26. int main()
  27. {
  28.     int user_choice, data;
  29.     char user_active = 'Y';
  30.  
  31.     while (user_active == 'Y' || user_active == 'y')
  32.     {
  33.         printf("\n--------> Queue Program <------\n");
  34.         printf("\n1. Enqueue");
  35.         printf("\n2. Dequeue");
  36.         printf("\n3. Display");
  37.         printf("\n4. Exit");
  38.  
  39.         printf("\n\nEnter your choice: ");
  40.         scanf("%d", &user_choice);
  41.  
  42.         switch(user_choice)
  43.         {
  44.             case 1:
  45.                 printf("\nEnter Data: ");
  46.                 scanf("%d", &data);
  47.                 enqueue(data);
  48.                 break;
  49.  
  50.             case 2:
  51.                 if (!isEmpty())
  52.                 {
  53.                     data = dequeue();
  54.                     printf("\n* %d was removed\n", data);
  55.                 }
  56.                 else
  57.                 {
  58.                     printf("\nQueue is Empty!\n");
  59.                 }
  60.                 break;
  61.  
  62.             case 3:
  63.                 display();
  64.                 printf("\n");
  65.                 break;
  66.  
  67.             case 4:
  68.                 printf("\n\tProgram was Terminated!\n\n");
  69.                 return 1;
  70.  
  71.             default:
  72.                 printf("\n\tInvalid Choice\n");
  73.         }
  74.  
  75.         printf("\nDo You want to continue? ");
  76.         fflush(stdin);
  77.         scanf(" %c", &user_active);
  78.     }
  79.     return 0;
  80. }
  81.  
  82.  
  83. // creates a new node
  84. struct node* create(int data)
  85. {
  86.     struct node* new_node = (struct node*) malloc (sizeof(struct node));
  87.     if (new_node == NULL)
  88.     {
  89.         printf("\n Memory can't be allocated\n");
  90.         return NULL;
  91.     }
  92.     new_node->data = data;
  93.     new_node->next = NULL;
  94.  
  95.     return new_node;
  96. }
  97.  
  98. // check if the queue is empty
  99. int isEmpty()
  100. {
  101.     if (front == NULL || rear == NULL)
  102.     {
  103.         return 1;
  104.     }
  105.     return 0;
  106. }
  107.  
  108. // inserts an item to the queue
  109. void enqueue(int data)
  110. {
  111.     struct node* new_node = create(data);
  112.  
  113.     if (new_node != NULL)
  114.     {
  115.         // if the queue is empty
  116.         if(front == NULL)
  117.         {
  118.             front = new_node;
  119.         }
  120.         else
  121.         {
  122.             rear->next = new_node;
  123.         }
  124.         // rear pointing to the new node
  125.         rear = new_node;
  126.         printf("\n* %d was inserted!\n", data);
  127.     }
  128. }
  129.  
  130. // removes an item to the queue
  131. int dequeue()
  132. {
  133.     if (!isEmpty())
  134.     {
  135.         int data = front->data;
  136.         front = front->next;
  137.         return data;
  138.     }
  139. }
  140.  
  141. // display the queue 
  142. void display()
  143. {
  144.     if (isEmpty())
  145.     {
  146.         printf("\nQueue is Empty!\n");
  147.         return;
  148.     }
  149.     printf("\n");
  150.     struct node* temp = front;
  151.     while (temp != NULL)
  152.     {
  153.         printf("%d ", temp->data);
  154.         temp = temp->next;
  155.     }
  156. }
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.

Linked List Implementation of the Queue - enqueue() Function

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

Linked List Implementation of the Queue - enqueue() Function

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.

Linked List Implementation of the Queue - dequeue() Function

Step 2: Move the front pointer to next node.

Linked List Implementation of the Queue - dequeue() Function

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”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.