A deque (double-ended queue) is a linear data structure that allows insertion and deletion of elements from both ends: front and rear. This flexibility makes it more versatile than a standard queue, and deques are widely used in task scheduling, caching, and sliding window algorithms. This article demonstrates array-based and linked-list-based deque implementations in C, including extended operations like getFront, getRear, isEmpty, size, and erase.
Understanding the Problem
A deque supports operations at both ends while maintaining element order. The challenge is correctly managing the front and rear pointers, especially in circular arrays or dynamically allocated linked lists. Proper handling prevents overflow, underflow, and invalid memory access. Utility functions such as getFront and getRear allow inspecting elements without removing them, while size and erase provide additional flexibility for managing the deque.
Program 1: Array-Based Deque
The array-based implementation uses a fixed-size array and modulo arithmetic to handle wrap-around. Insertion and deletion can be performed at both ends efficiently. Overflow and underflow are checked to prevent invalid operations, and the utility functions allow easy inspection and management of the deque.
#include <stdio.h>
#define MAX 5
int deque[MAX];
int front = -1, rear = -1;
int isEmpty() {
return front == -1;
}
int isFull() {
return (front == 0 && rear == MAX - 1) || (front == rear + 1);
}
void insertFront(int value) {
if (isFull()) {
printf("Deque Overflow! Cannot insert %d\n", value);
return;
}
if (isEmpty())
front = rear = 0;
else if (front == 0)
front = MAX - 1;
else
front--;
deque[front] = value;
printf("%d inserted at front\n", value);
}
void insertRear(int value) {
if (isFull()) {
printf("Deque Overflow! Cannot insert %d\n", value);
return;
}
if (isEmpty())
front = rear = 0;
else
rear = (rear + 1) % MAX;
deque[rear] = value;
printf("%d inserted at rear\n", value);
}
void deleteFront() {
if (isEmpty()) {
printf("Deque Underflow! Nothing to delete.\n");
return;
}
printf("%d deleted from front\n", deque[front]);
if (front == rear)
front = rear = -1;
else
front = (front + 1) % MAX;
}
void deleteRear() {
if (isEmpty()) {
printf("Deque Underflow! Nothing to delete.\n");
return;
}
printf("%d deleted from rear\n", deque[rear]);
if (front == rear)
front = rear = -1;
else if (rear == 0)
rear = MAX - 1;
else
rear--;
}
int getFront() {
if (isEmpty()) {
printf("Deque is empty\n");
return -1;
}
return deque[front];
}
int getRear() {
if (isEmpty()) {
printf("Deque is empty\n");
return -1;
}
return deque[rear];
}
int size() {
if (isEmpty())
return 0;
if (rear >= front)
return rear - front + 1;
return MAX - (front - rear - 1);
}
void erase() {
front = rear = -1;
printf("Deque cleared\n");
}
void display() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
int i = front;
printf("Deque elements: ");
while (1) {
printf("%d ", deque[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf("\n");
}
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
display();
printf("Front: %d, Rear: %d, Size: %d\n", getFront(), getRear(), size());
deleteFront();
display();
insertRear(30);
insertFront(1);
display();
printf("Front: %d, Rear: %d, Size: %d\n", getFront(), getRear(), size());
erase();
display();
return 0;
}The array-based deque efficiently handles insertions and deletions at both ends while allowing quick access to the front and rear elements. The size and erase functions provide further convenience for managing the deque’s contents.
Program 2: Linked-List-Based Deque
The linked-list implementation allows dynamic memory allocation and unlimited size. Each node contains data and pointers to the previous and next elements, enabling efficient insertions and deletions at both ends. Utility functions provide inspection and management without removing elements, and the erase function clears the entire deque safely.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
Node *front = NULL, *rear = NULL;
int isEmpty() {
return front == NULL;
}
void insertFront(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = front;
if (!front)
rear = newNode;
else
front->prev = newNode;
front = newNode;
printf("%d inserted at front\n", value);
}
void insertRear(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = rear;
if (!rear)
front = newNode;
else
rear->next = newNode;
rear = newNode;
printf("%d inserted at rear\n", value);
}
void deleteFront() {
if (isEmpty()) {
printf("Deque Underflow! Nothing to delete.\n");
return;
}
Node *temp = front;
printf("%d deleted from front\n", front->data);
front = front->next;
if (front)
front->prev = NULL;
else
rear = NULL;
free(temp);
}
void deleteRear() {
if (isEmpty()) {
printf("Deque Underflow! Nothing to delete.\n");
return;
}
Node *temp = rear;
printf("%d deleted from rear\n", rear->data);
rear = rear->prev;
if (rear)
rear->next = NULL;
else
front = NULL;
free(temp);
}
int getFront() {
if (isEmpty()) {
printf("Deque is empty\n");
return -1;
}
return front->data;
}
int getRear() {
if (isEmpty()) {
printf("Deque is empty\n");
return -1;
}
return rear->data;
}
int size() {
int count = 0;
Node *temp = front;
while (temp) {
count++;
temp = temp->next;
}
return count;
}
void erase() {
Node *temp;
while (front) {
temp = front;
front = front->next;
free(temp);
}
rear = NULL;
printf("Deque cleared\n");
}
void display() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
Node *temp = front;
printf("Deque elements: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
display();
printf("Front: %d, Rear: %d, Size: %d\n", getFront(), getRear(), size());
deleteFront();
display();
insertRear(30);
insertFront(1);
display();
printf("Front: %d, Rear: %d, Size: %d\n", getFront(), getRear(), size());
erase();
display();
return 0;
}The linked-list deque allows unlimited growth while keeping insertion and deletion operations efficient. The added utility functions make it easy to inspect and manage elements without modifying the deque.
FAQs
Q1: What is the time complexity of operations in a deque?
Insertion and deletion at both ends are O(1) for both array and linked-list implementations.
Q2: When should a linked-list deque be preferred over an array deque?
Use linked lists when the maximum size is unknown or dynamic resizing is needed. Arrays are simpler for fixed-size deques.
Q3: Can a deque be used as a stack or queue?
Yes, a deque can simulate a stack (LIFO) or a queue (FIFO) by restricting operations to one end or using both ends strategically.
Q4: What are common applications of deques?
Deques are used in sliding window problems, undo/redo operations in editors, and cache implementations (like LRU cache).
Conclusion
Deques are highly versatile data structures that support operations at both ends. Array-based deques are efficient for small fixed-size applications, while linked-list deques provide dynamic sizing and unlimited growth. Proper pointer management and memory handling ensure that deque operations are performed safely and efficiently. The extended operations getFront, getRear, isEmpty, size, and erase enhance usability, making it easy to manage deque contents in practical applications.
References & Additional Resources
A curated collection of textbooks and tutorials for learning deque (double-ended queue) implementations in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference covering C fundamentals, arrays, pointers, and memory management essential for deque implementations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of deque concepts, including array- and linked-list-based implementations with practical examples.
- GeeksforGeeks: Deque Using Arrays in C – Step-by-step explanation and code for implementing deques using arrays.
- GeeksforGeeks: Deque Using Linked List – Guide for implementing deques using doubly linked lists.
- Programiz: Queue and Deque Data Structures – Practical guide and C examples for deque operations.
- C Standard Library Documentation – Official reference for standard C functions and libraries often used in deque operations.
