Dequeuer

Dequeuer

Description: A dequeuer, more commonly referred to as a deque (pronounced "deck"), is a double-ended queue that allows insertion and deletion of elements from both the front and the back. This flexibility makes deques more versatile than standard queues, which only allow operations at one end.

Basic Operations

1. Enqueue Front: Add an element to the front of the deque.
2. Enqueue Back: Add an element to the back of the deque.
3. Dequeue Front: Remove an element from the front of the deque.
4. Dequeue Back: Remove an element from the back of the deque.
5. Front/Peek: Get the element at the front without removing it.
6. Back/Peek: Get the element at the back without removing it.
7. IsEmpty: Check if the deque is empty.
8. Size: Get the number of elements in the deque.

Time Complexity

• Enqueue Front: $O(1)$
• Enqueue Back: $O(1)$
• Dequeue Front: $O(1)$
• Dequeue Back: $O(1)$
• Front/Peek: $O(1)$
• Back/Peek: $O(1)$
• IsEmpty: $O(1)$
• Size: $O(1)$

Implementations

Deques can be implemented using:

1. Doubly Linked List: Provides efficient insertion and deletion from both ends.
2. Circular Array: Allows for dynamic sizing while managing space efficiently.

Example Code (Using Doubly Linked List)

Here’s a simple C++ implementation of a deque using a doubly linked list:

#include <iostream>
using namespace std;

// Node structure for doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;
};

// Deque class
class Deque {
private:
    Node* front;
    Node* rear;
    int size;

public:
    Deque() : front(nullptr), rear(nullptr), size(0) {}

    // Add an element at the front
    void enqueueFront(int value) {
        Node* newNode = new Node{value, nullptr, front};
        if (front) {
            front->prev = newNode;
        }
        front = newNode;
        if (!rear) {
            rear = front; // If the deque was empty, rear is also the new node
        }
        size++;
    }

    // Add an element at the back
    void enqueueBack(int value) {
        Node* newNode = new Node{value, rear, nullptr};
        if (rear) {
            rear->next = newNode;
        }
        rear = newNode;
        if (!front) {
            front = rear; // If the deque was empty, front is also the new node
        }
        size++;
    }

    // Remove an element from the front
    int dequeueFront() {
        if (isEmpty()) {
            throw runtime_error("Deque is empty");
        }
        int value = front->data; // Get the data from the front node
        Node* temp = front;
        front = front->next;
        if (front) {
            front->prev = nullptr; // Update the new front's previous pointer
        } else {
            rear = nullptr; // If deque is now empty, update rear as well
        }
        delete temp;
        size--;
        return value;
    }

    // Remove an element from the back
    int dequeueBack() {
        if (isEmpty()) {
            throw runtime_error("Deque is empty");
        }
        int value = rear->data; // Get the data from the rear node
        Node* temp = rear;
        rear = rear->prev;
        if (rear) {
            rear->next = nullptr; // Update the new rear's next pointer
        } else {
            front = nullptr; // If deque is now empty, update front as well
        }
        delete temp;
        size--;
        return value;
    }

    // Peek at the front element
    int peekFront() {
        if (isEmpty()) {
            throw runtime_error("Deque is empty");
        }
        return front->data;
    }

    // Peek at the back element
    int peekBack() {
        if (isEmpty()) {
            throw runtime_error("Deque is empty");
        }
        return rear->data;
    }

    // Check if the deque is empty
    bool isEmpty() {
        return size == 0;
    }

    // Get the size of the deque
    int getSize() {
        return size;
    }

    ~Deque() {
        while (!isEmpty()) {
            dequeueFront(); // Dequeue all elements to free memory
        }
    }
};

int main() {
    Deque dq;

    // Adding elements
    dq.enqueueBack(10);
    dq.enqueueBack(20);
    dq.enqueueFront(5);
    dq.enqueueFront(2);

    cout << "Front element: " << dq.peekFront() << endl; // Should print 2
    cout << "Back element: " << dq.peekBack() << endl;   // Should print 20

    cout << "Dequeued from front: " << dq.dequeueFront() << endl; // Should remove 2
    cout << "Dequeued from back: " << dq.dequeueBack() << endl;   // Should remove 20

    cout << "Size of deque: " << dq.getSize() << endl; // Should print 2

    return 0;
}

Explanation of the Code

1. Node Structure: Each node holds data and pointers to both the previous and next nodes.
2. Deque Class: Manages pointers for the front and rear of the deque and tracks the size.
   • enqueueFront: Adds a new node at the front.
   • enqueueBack: Adds a new node at the back.
   • dequeueFront: Removes the front node and returns its data.
   • dequeueBack: Removes the back node and returns its data.
   • peekFront: Returns the data at the front without removing it.
   • peekBack: Returns the data at the back without removing it.
   • isEmpty: Checks if the deque is empty.
   • getSize: Returns the current number of elements in the deque.
3. Destructor: Ensures all nodes are properly deleted when the deque is no longer in use.
4. Main Function: Demonstrates deque operations, including adding and removing elements from both ends.

Conclusion

Deques provide a flexible way to manage data with operations available at both ends, making them useful in various applications such as task scheduling, caching, and implementing algorithms that require efficient access to both ends of a data structure. Understanding how to implement and use deques is essential for effective problem-solving in programming.