Basic Operations on C Double-Ended Queue
We can perform the following basic operations in a double-ended queue:
Operation | Description | Time Complexity | Space Complexity |
---|---|---|---|
Insertion at front | This function is used to insert an element at the front end of the deque. | O(1) | O(1) |
Insertion at rear | This function is used to insert an element at the rear end of the deque. | O(1) | O(1) |
Deletion at front | This function is used to delete an element from the front end of the deque. | O(1) | O(1) |
Deletion at rear | This function is used to delete an element from the rear end of the deque. | O(1) | O(1) |
Check empty | This function is used to check if the deque is empty or not. | O(1) | O(1) |
Check full | This function is used to check if the deque is full or not. | O(1) | O(1) |
Here, front denotes the first element of the deque and rear denotes the last element of the deque.
Before performing these operations, we must follow the below two steps:
- Declare an array(to be used as a deque) of size N.
- Set two pointers at first position i.e. front = -1 and rear = 0
1. Insertion at Front in Deque in C
To insert an element at the front end of the deque first, check if the deque is full or not if deque is not full then follow the below approach:
Approach:
- First, check the position of the front in our array.
- If front < 1 , reinitialize front as the last index of the array i.e. front = N-1.
- Then, add new element to array[front].
2. Insertion at Rear in Deque in C
To insert an element at the rear end of the deque, follow the below approach:
Approach:
- First, check if the deque is full or not.
- If the deque is full , reinitialize rear with 0 (rear = 0) else increase rear by 1.
- Then, add the element to array[rear].
3. Deletion at Front in Deque in C
To delete an element at the front end of the deque first, follow the below approach:
Approach:
- First, check if deque is empty or not.
- If the deque is empty (front == -1), then we cannot perform deletion operation. In this condition, we will simply print undeflow.
- If deque contains only 1 element (front = rear) , then only one deletion operation can be performed. set front = -1 and rear = -1.
- Else if the front is at the last index ( front == n-1 ) , set front at starting index of deque (front = 0).
- If none of the above case exists, just increment front by 1 (front = front + 1).
4. Deletion at Rear in Deque in C
To delete an element at the rear end of the deque, follow the below approach:
- First, check if the deque is empty or not.
- If the deque is empty (front = -1), then deletion operation cannot be performed and we will print underflow.
- If the deque has only 1 element( front==rear), we will set front = -1 and rear =-1.
- If the rear is at the starting index of deque (rear == 0) , then set rear to last index (rear = n-1).
- If none of the above case exists, just decrement rear by 1 (rear = rear-1).
Check if Deque is Empty or Not Empty
To check if the deque is empty simply check the front if front = -1, then deque is empty else it is not empty.
Check if Deque is Full or Not Full
To check if the deque is full simply check the below conditions:
- If front == 0 and rear == n-1 , then deque is Full
- If front == rear + 1 , then also deque is Full.
C implementation Double-Ended Queue
The double-ended queues, called deques for short, are a generalized form of the queue. It is exactly like a queue except that it does not follow the FIFO rule (First in first out) so, the elements can be added to or removed from either the front(head) or back(tail) of the deque.
In this article, we will learn about the double-ended queue implementation in C. We will also look at the working of the double-ended queue and the basic operations that can be performed using the double-ended queue in C.
Contact Us