.png)
[Follow here] for daily coding insights.
DSA Series Chapter 8– Deque (Double-Ended Queue) in C
1. What is a Deque?
A Deque (pronounced as “deck” or Double-Ended Queue) is a linear data structure in which insertion and deletion can be performed from both the front and the rear. This post explains types, operations, applications, array implementation and complete C programs with step-by-step explanations.in which:
✔ You can insert at both:
-
Front
-
Rear
✔ You can delete from both:
-
Front
-
Rear
Thus, it overcomes the limitations of normal queues and circular queues.
2. Types of Deques
(i) Input Restricted Deque
-
Insert: only at rear
-
Delete: either front or rear
(ii) Output Restricted Deque
-
Insert: at front or rear
-
Delete: only at front
3. Operations of Deque
| Operation | Description |
|---|---|
insertFront(x) |
Insert element at front |
insertRear(x) |
Insert element at rear |
deleteFront() |
Delete element from front |
deleteRear() |
Delete element from rear |
getFront() |
Returns front element |
getRear() |
Returns rear element |
isFull() |
Checks if deque is full |
isEmpty() |
Checks if deque is empty |
4. Array Implementation of Deque in C (Circular Logic)
4.1 Why Circular Logic?
If we use linear indexing, front and rear cannot move after reaching boundaries.
Circular indexing solves this using:
(front - 1 + size) % size
(rear + 1) % size
5. Deque Implementation in C (Array Version)
📌 Full C Program — Array Based Deque (Very Detailed)
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
struct Deque {
int arr[SIZE];
int front;
int rear;
};
// Function to initialize deque
void initialize(struct Deque *dq) {
dq->front = -1;
dq->rear = -1;
}
// Check if deque is full
int isFull(struct Deque *dq) {
return ((dq->front == 0 && dq->rear == SIZE - 1) ||
(dq->front == dq->rear + 1));
}
// Check if deque is empty
int isEmpty(struct Deque *dq) {
return (dq->front == -1);
}
// Insert at front
void insertFront(struct Deque *dq, int x) {
if (isFull(dq)) {
printf("Deque Overflow!\n");
return;
}
// First element
if (dq->front == -1) {
dq->front = dq->rear = 0;
}
// If front is at first position, move it to last
else if (dq->front == 0) {
dq->front = SIZE - 1;
}
else {
dq->front--;
}
dq->arr[dq->front] = x;
printf("Inserted %d at front\n", x);
}
// Insert at rear
void insertRear(struct Deque *dq, int x) {
if (isFull(dq)) {
printf("Deque Overflow!\n");
return;
}
// First element
if (dq->rear == -1) {
dq->front = dq->rear = 0;
}
else if (dq->rear == SIZE - 1) {
dq->rear = 0;
}
else {
dq->rear++;
}
dq->arr[dq->rear] = x;
printf("Inserted %d at rear\n", x);
}
// Delete from front
void deleteFront(struct Deque *dq) {
if (isEmpty(dq)) {
printf("Deque Underflow!\n");
return;
}
printf("Deleted %d from front\n", dq->arr[dq->front]);
if (dq->front == dq->rear) {
dq->front = dq->rear = -1; // deque becomes empty
}
else if (dq->front == SIZE - 1) {
dq->front = 0;
}
else {
dq->front++;
}
}
// Delete from rear
void deleteRear(struct Deque *dq) {
if (isEmpty(dq)) {
printf("Deque Underflow!\n");
return;
}
printf("Deleted %d from rear\n", dq->arr[dq->rear]);
if (dq->front == dq->rear) {
dq->front = dq->rear = -1; // deque becomes empty
}
else if (dq->rear == 0) {
dq->rear = SIZE - 1;
}
else {
dq->rear--;
}
}
// Get front element
int getFront(struct Deque *dq) {
if (!isEmpty(dq))
return dq->arr[dq->front];
printf("Deque is empty!\n");
return -1;
}
// Get rear element
int getRear(struct Deque *dq) {
if (!isEmpty(dq))
return dq->arr[dq->rear];
printf("Deque is empty!\n");
return -1;
}
int main() {
struct Deque dq;
initialize(&dq);
insertRear(&dq, 10);
insertRear(&dq, 20);
insertFront(&dq, 5);
insertFront(&dq, 3);
printf("Front element: %d\n", getFront(&dq));
printf("Rear element: %d\n", getRear(&dq));
deleteFront(&dq);
deleteRear(&dq);
return 0;
}
6. Explanation of Key Concepts
6.1 Structure Explanation
struct Deque {
int arr[SIZE];
int front;
int rear;
};
-
arr[]→ stores elements -
front→ index of the first element -
rear→ index of the last element
6.2 Circular Movement
If front/rear reaches boundary:
front = SIZE - 1 → goes to last
rear = 0 → goes to first
6.3 Overflow Condition
(front == 0 && rear == SIZE - 1) ||
(front == rear + 1)
6.4 Underflow Condition
front == -1
7. Time & Space Complexity
| Operation | Complexity |
|---|---|
| Insert Front | O(1) |
| Insert Rear | O(1) |
| Delete Front | O(1) |
| Delete Rear | O(1) |
| Get Front/Rear | O(1) |
| Space | O(n) |
8. Applications of Deque
-
Browser history navigation
-
Task scheduling
-
Palindrome checking
-
Sliding window maximum algorithm
-
Aho-Corasick string matching
ALSO CHECK
ALSO CHECK
Comments
Post a Comment