Basic Operations of Queue in C
Following are the basic operations of a Queue that are used frequently to manipulate the elements present inside the queue:
Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
Enqueue | Inserts an element in the queue through rear pointer. | O(1) | O(1) |
Dequeue | Removes an element from the queue through front pointer. | O(1) | O(1) |
Peek | Returns the front element of the queue. | O(1) | O(1) |
IsFull | Returns true is the queue is full otherwise returns false. | O(1) | O(1) |
IsEmpty | Returns true is the queue is empty otherwise returns false. | O(1) | O(1) |
Just like stack, the queue also offers all its operation in constant time. Let’s see how to implement these basic operations for our queue in C.
1. isFull Function
The isFull function will check whether the queue is full or not. As rear will always be pointing to the leftmost empty element, if the rear gets greater than or equal to the MAX_SIZE, it means that it already contains the maximum possible number of elements.
Algorithm of isFull Function
Following is the algorithm for isFull Function:
- If rear == MAX_SIZE, return true.
- Else, return false.
2. isEmpty Function
The isEmpty function will check whether the queue is empty or not. When we initialize a queue, we set the front = -1 and rear = 0. So we know that when there are no elements in the queue, the front = rear – 1.
Algorithm of isEmpty Function
Following is the algorithm for isFull Function:
- If front == rear – 1, return true.
- Else, return false
3. Enqueue Function
The enqueue functions inserts an element to the queue through the rear pointer. We need to check for queue overflow (queue already full) before adding the new element.
Algorithm of Enqueue Function
Following is the algorithm for the enqueue function:
- Check whether the queue is full.
- If the queue is full, display the overflow message.
- If the queue is not full, add the new element to the position pointed to by the rear pointer.
- Increment the rear pointer.
4. Dequeue Function
The enqueue functions removes an element from the front of the queue through the front pointer. We need to check for the queue underflow (queue is already empty) condition before trying to dequeu the front element.
Algorithm of Dequeue
Following is the algorithm for the dequeue function:
- Check whether the queue is empty.
- If the queue is empty, display the underflow message.
- If the queue is not empty,
- Increment the front pointer of the queue.
- remove the element at the front position.
5. Peek Function
The peek functions returns the front most element of the queue. If the queue is empty it returns -1.
Algorithm of Peek Function
Following is the algorithm for the dequeue function:
- Check if the queue is empty.
- If the queue is empty, return -1.
- If not, return queueArray[front + 1].
Queue in C
A queue is a linear data structure that follows the First In First Out (FIFO) order of insertion and deletion. It means that the element that is inserted first will be the first one to be removed and the element that is inserted last will be removed at last.
In this article, we’ll learn how to implement the queue data structure in the C programming language. We will also look at some of its basic operations along with their time and space complexity analysis.