Queue in C

Operations Associated with a Queue in C

We implement a queue in C using an array. To use an array as a queue in C, we need to define the operations that are characteristic of the queue data structure.

The following operations can be performed in queue:

1. Front
2. Rear
3. isEmpty()
4. isFull()
5. peek()
6. size()
7. enqueue()
8. dequeue()

Let us look at the working and importance of all these operations in detail.

1. Front

We discussed in the previous section, that any new element to be inserted will be inserted at the back of the queue, and all deletion operations take place from the front of the queue. For this reason, we will need a pointer to the front of the queue, so that when we need to delete an element we can do the operation quickly.

Hence, the front variable points to the position of the first element of the queue for quick deletion operation.

In C, when we use an array to implement a queue, the front variable will store the index of the first element of the queue. It is initialized with a value of -1 as the queue is empty initially.

2. Rear

Just like we need a front variable for the deletion operation, we would also need a variable that points to the back of the queue, so that we know where the new element needs to be inserted in case of an insertion operation, as new elements are inserted at the back of the queue. Hence, the rear variable points to the position of the last element of the queue for quick insertion operation.

In C, when we use an array to implement a queue, the rear variable will store the index of the last element of the queue. It is initialized with a value of -an 1 as the queue is empty initially.

3. isEmpty()

This operation, as the name suggests, checks if the queue is empty. This operation comes in handy when we want to perform a deletion operation, we can check first if the queue is empty and perform the operation only if the queue has elements.

In C, when we use an array to implement a queue, this will happen when both front and rear are -1. The time complexity of this operation is $O(1)$.

4. isFull()

This operation, as the name suggests, checks if the queue is at full capacity. This operation comes in handy when we want to perform an insertion operation, we can check k first if the queue is full and perform the operation only if the queue has space for additional elements.

In C, when we use an array to implement a queue, we will have to declare a size for the array, and the queue will be full when rear = sizeof(array)-1, which means that the rear variable points to the last position in the array. The time complexity of this operation is $O(1)$.

5. peek()

This operation is used to just access the first element of the queue. So, whenever we call this function, it returns the value of the first element in our queue, if the queue is not empty.

In this operation, we also have to check if the queue is empty or not. If it is empty then we cannot possibly return the first element. Otherwise, we just return the element at the front index. The time complexity of this operation is $O(1)$.

6. size()

This operation is used to return the size of the queue. In C when we implement the queue using an array, we just need to return the difference between the rear and front variables + 1, as that will be the number of elements, except the case when front = rear = -1. The time complexity of this operation is $O(1)$.

7. enqueue()

This operation is used to insert a new element into the queue in C. As mentioned before, the queue follows a FIFO order, and hence any new elemin ent which is to be inserted should be inserted at the very end of the queue. To insert a new element at the end of the queue, we make use of the rear pointer, which already points to the end of the queue.

In this operation, we also need to check if the queue is at its full capacity, if not then we insert a new element at the very end of the queue and update the rear variable to point to the new end of the queue, which is the element we just inserted. In case this is the first element is inserted, we also need to set the front value to 0. In C, when we use an array to implement a queue, we increment the rear variable. The time complexity of this operation is $O(1)$.

8. dequeue()

This operation is used to delete a data element from the queue in C. As mentioned before, the queue follows a FIFO order, and hence if we want to delete an element it has to be the first element of the queue. To delete a data element from the front of the queue, we make use of the front pointer, which already points to the front of the queue.

In this operation, we also need to check if the queue is initially empty, if not then we can delete an element from the start and update the front variable to point to the element that is now at the front of the queue, this will be the element that was in the second place in the queue before the deletion operation took place. In C, when we use an array to implement a queue, we erase the value at the front index and then we increment the front variable.

Now, there can be a case where we delete all elements in the queue, and in that case, the value of the front variable will exceed the value of the rear variable because in the process of deletion, we keep increasing the front variable, but the rear variable remains the same. This means that the queue is now empty, and we should reset the front and rear variable to -1. The time complexity of this operation is $O(1)$.

Example

Let us look at an example to understand all these operations better. Consider a queue initialized using an array of maximum size 6.

1. Initially, the array queue[6] is completely empty. We initialize the front and rear variables to -1.
2. enqueue(23): We add 23 to the queue. As this is the first element, we update front = 0, then increment rear so that rear = 0, and then assign queue[rear] = 23.
3. enqueue(12): We add 12 to the queue. We first increment rear so that rear = 1, and then assign queue[rear] = 12.
4. dequeue(): We assign queue[front] = 0, i.e, queue[0] = 0 and increment front so that front =update
5. enqueue(10): We add 10 to the queue. We first increment rear so that rear = 2, and then assign queue[rear] = 10.
6. dequeue(): We assign queue[front] = 0, i.e, queue[1] = 0 and increment front so that front = 2.
7. dequeue(): We assign queue[front] = 0, i.e, queue[2] = 0 and increment front so that front = 3. Now, the point to note is that rear = 2, so front>rear and the queue is empty so we reset front = -1 and rear = -1.

Types of Queues

Queues can be classified into 4 different types. Let's discuss each of them:

1. Simple Queue:

   • In a simple queue, we follow the First In, First Out (FIFO) rule. Insertion takes place at one end, i.e., the rear end or the tail of the queue, and deletion takes place at the other end, i.e., the front end or the head of the queue.
   • The time complexity of a simple queue is O(1) for insertion and deletion operations.

2. Circular Queue:

   • A circular queue exhibits similar characteristics to that of a simple queue, with the additional property of joining the front end to the rear end.
   • It follows the FIFO rule where the rear is connected to the end.
   • It is also known as the ring buffer.
   • The time complexity of a circular queue is O(1) for insertion and deletion.
   • More information can be found at Circular Queue in Data Structure.

3. Priority Queue:

   • A priority queue also exhibits similar characteristics to that of a simple queue where each element is assigned a particular priority value, where elements in the queue are assigned based on priority.

   • There are 2 types of priority queues:

     • Ascending Order: In this priority queue, the elements are arranged in ascending order of their priority, i.e., the element with the smallest priority comes at the start, and the element with the greatest priority comes at the end.
     • Descending Order: In this priority queue, the elements are arranged in descending order of their priority, i.e., the element with the greatest priority is at the start and the element with the smallest priority is present at the end of the queue.

   • For insertion and deletion, the priority queue has a time complexity of O(logn).

   • More information can be found at Priority Queue in Data Structure.

4. Double Ended Queue:

   • A Double-ended Queue, or Deque, is a different type of queue where enqueue (insertion) and dequeue (deletion) operations are performed at both the ends, i.e., the rear-end (tail) and the front-end (head). The Deque
   • can further be divided into 2 special queues, i.e., Input-restricted Deque and Output-Restricted Deque.
   • The time complexity of a double-ended queue is O(1) for insertion and deletion.

Learn more about the Types of Queues on Scaler Topics.

Implementation of Queue Using Array

Output

Click here to learn more.

Implementation of Queue Using Stacks

Output

Implementation of Queue Using Linked List

Output

Learn more on Scaler Topics.

Applications of Queue

The various applications of queues in the real world are:

• The operating system uses queues to store the order of execution of processes in CPU scheduling and Disk scheduling.
• Interrupts in a system are handled using queues, as the interrupts have to be addressed in the order they arrive, hence the FIFO principle is best for this purpose.
• When there is a single shared resource but multiple user requests, these requests are processed by using a queue.
• Queues are also the preferred data structure for synchronization, for example in I/O buffers or pipes.
• In real life, queues are used in call centers to process the calls coming in from the customers, on a first come first serve basis.

Limitations of Queue in C

The method of implementing queue in C seems good enough. However, this method has its limitations. If we look into closely, the available space to store the elements reduces after a few insertion and deletion operations. For example, initially, the queue, of size 5, was empty, then we add three elements to it: 1, 2, and 3.

The front variable points to index 0, while the rear variable points to index 2. Now, if we delete two elements the queue will be left with only element 3, and the front, as well as the rear, will point to index 2. Adding two more elements to the queue: 4 and5 the queue is now 3, 4, 5, and the front points to index 2, while the rear points to index 4. This means that if we now try adding another element, we will get a message that the queue is full. But the first two indexes, i.e. 0 and 1 are empty.

This is exactly why even though we have space in the queue, we cannot insert more elements in tare his method. To overcome this limitation, we can make use of circular queues.