C Program to Implement Double-Ended Queue (Deque)

Introduction

A double-ended queue, or deque (pronounced "deck"), is a linear data structure that allows insertion and deletion of elements from both ends (i.e., front and rear). This makes the deque more flexible than a standard queue, which only allows operations at one end. Deques can be used in various applications, such as implementing undo mechanisms, managing resources, and more.

Example:

• Input: Insert elements at both ends of the deque.
• Output: Elements can be deleted from both ends, following the operations performed.

Problem Statement

Create a C program that:

• Implements a double-ended queue (deque) using an array.
• Performs operations like inserting and deleting elements from both ends.
• Displays the contents of the deque.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions.
2. Define Constants and Global Variables: Define the maximum size of the deque and variables to keep track of the front and rear indices.
3. Implement the Deque Operations:

• Insert at Front: Add an element to the front of the deque.
• Insert at Rear: Add an element to the rear of the deque.
• Delete from Front: Remove an element from the front of the deque.
• Delete from Rear: Remove an element from the rear of the deque.
• Display: Display all elements in the deque.
• IsEmpty: Check if the deque is empty.
• IsFull: Check if the deque is full.

4. Create a Main Function: In the main() function, allow the user to perform deque operations interactively.

C Program to Implement Double-Ended Queue (Deque)

#include <stdio.h> #include <stdlib.h> #define MAX 5 // Maximum size of the deque int deque[MAX]; int front = -1; int rear = -1; // Function to check if the deque is empty int isEmpty() { return front == -1; } // Function to check if the deque is full int isFull() { return (front == 0 && rear == MAX - 1) || (front == rear + 1); } // Function to insert an element at the front of the deque void insertFront(int value) { if (isFull()) { printf("Deque overflow! Cannot insert %d at the front.\n", value); return; } if (isEmpty()) { // First element insertion front = rear = 0; } else if (front == 0) { front = MAX - 1; } else { front--; } deque[front] = value; printf("%d inserted at the front.\n", value); } // Function to insert an element at the rear of the deque void insertRear(int value) { if (isFull()) { printf("Deque overflow! Cannot insert %d at the rear.\n", value); return; } if (isEmpty()) { // First element insertion front = rear = 0; } else if (rear == MAX - 1) { rear = 0; } else { rear++; } deque[rear] = value; printf("%d inserted at the rear.\n", value); } // Function to delete an element from the front of the deque int deleteFront() { if (isEmpty()) { printf("Deque underflow! Cannot delete from the front.\n"); return -1; } int deleted_value = deque[front]; if (front == rear) { // Only one element was present front = rear = -1; } else if (front == MAX - 1) { front = 0; } else { front++; } printf("Deleted %d from the front.\n", deleted_value); return deleted_value; } // Function to delete an element from the rear of the deque int deleteRear() { if (isEmpty()) { printf("Deque underflow! Cannot delete from the rear.\n"); return -1; } int deleted_value = deque[rear]; if (front == rear) { // Only one element was present front = rear = -1; } else if (rear == 0) { rear = MAX - 1; } else { rear--; } printf("Deleted %d from the rear.\n", deleted_value); return deleted_value; } // Function to display the elements of the deque void display() { if (isEmpty()) { printf("Deque is empty!\n"); return; } printf("Deque elements: "); int i = front; while (1) { printf("%d ", deque[i]); if (i == rear) { break; } i = (i + 1) % MAX; } printf("\n"); } int main() { int choice, value; while (1) { // Provide a menu for deque operations printf("\nDeque Operations Menu:\n"); printf("1. Insert at Front\n"); printf("2. Insert at Rear\n"); printf("3. Delete from Front\n"); printf("4. Delete from Rear\n"); printf("5. Display\n"); printf("6. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter value to insert at front: "); scanf("%d", &value); insertFront(value); break; case 2: printf("Enter value to insert at rear: "); scanf("%d", &value); insertRear(value); break; case 3: deleteFront(); break; case 4: deleteRear(); break; case 5: display(); break; case 6: exit(0); default: printf("Invalid choice! Please enter a valid option.\n"); } } return 0; // Return 0 to indicate successful execution } 

Explanation

Step 2: Define Constants and Global Variables

• The MAX constant defines the maximum size of the deque.
• The deque array holds the elements of the deque, and front and rear are used to track the front and rear indices of the deque.

Function to Check if the Deque is Empty

• The isEmpty function returns 1 if both front and rear are -1, indicating the deque is empty; otherwise, it returns 0.

Function to Check if the Deque is Full

• The isFull function checks if the deque is full by verifying whether front is 0 and rear is MAX - 1 (meaning the deque is full from the start to the end) or if front is immediately after rear (meaning the deque has wrapped around).

Function to Insert an Element at the Front of the Deque

• The insertFront function inserts an element at the front of the deque. It adjusts the front index to wrap around if necessary.

Function to Insert an Element at the Rear of the Deque

• The insertRear function inserts an element at the rear of the deque. It adjusts the rear index to wrap around if necessary.

Function to Delete an Element from the Front of the Deque

• The deleteFront function removes and returns the front element from the deque. It adjusts the front index to wrap around if necessary.

Function to Delete an Element from the Rear of the Deque

• The deleteRear function removes and returns the rear element from the deque. It adjusts the rear index to wrap around if necessary.

Function to Display the Elements of the Deque

• The display function prints all elements in the deque from front to rear.

Main Function

• The main function provides a menu-driven interface allowing the user to perform various deque operations interactively.

Output Example

Example Output:

Deque Operations Menu: 1. Insert at Front 2. Insert at Rear 3. Delete from Front 4. Delete from Rear 5. Display 6. Exit Enter your choice: 1 Enter value to insert at front: 10 10 inserted at the front. Deque Operations Menu: 1. Insert at Front 2. Insert at Rear 3. Delete from Front 4. Delete from Rear 5. Display 6. Exit Enter your choice: 2 Enter value to insert at rear: 20 20 inserted at the rear. Deque Operations Menu: 1. Insert at Front 2. Insert at Rear 3. Delete from Front 4. Delete from Rear 5. Display 6. Exit Enter your choice: 5 Deque elements: 10 20 Deque Operations Menu: 1. Insert at Front 2. Insert at Rear 3. Delete from Front 4. Delete from Rear 5. Display 6. Exit Enter your choice: 3 Deleted 10 from the front. 

Conclusion

This C program demonstrates how to implement a double-ended queue (deque) using an array. It handles basic operations such as inserting and deleting elements from both ends of the deque, making it a useful example for understanding deque operations and

circular array implementation in C programming.