Deque Implementation in CPP

1. Introduction

A Deque, short for "double-ended queue," is a linear data structure that allows the insertion and removal of elements from both the front and the rear. It combines the capabilities of both stacks and queues. In this blog post, we'll walk through implementing a deque using C++.

2. Implementation Steps

1. Utilize the C++ Standard Library to include the deque header.

2. Declare a Deque class.

3. Define methods for adding an item to the front (push_front), adding an item to the rear (push_back), removing the front item (pop_front), removing the rear item (pop_back), viewing the front item (front), and viewing the rear item (back).

4. Showcase the usage of the Deque with a demonstration.

3. Implementation in C++ Programming

#include<iostream>
#include<deque>  // For std::deque
class Deque {
private:
    std::deque<int> dq;
public:
    void push_front(int item) {
        dq.push_front(item);
    }
    void push_back(int item) {
        dq.push_back(item);
    }
    void pop_front() {
        if(!dq.empty()) dq.pop_front();
        else cout << "Deque is empty!" << endl;
    }
    void pop_back() {
        if(!dq.empty()) dq.pop_back();
        else cout << "Deque is empty!" << endl;
    }
    int front() {
        if(!dq.empty()) return dq.front();
        cout << "Deque is empty!" << endl;
        return -1; // Error value
    }
    int back() {
        if(!dq.empty()) return dq.back();
        cout << "Deque is empty!" << endl;
        return -1; // Error value
    }
};
int main() {
    Deque dq;
    dq.push_front(10);
    dq.push_back(30);
    cout << "Front of Deque: " << dq.front() << endl;
    cout << "Back of Deque: " << dq.back() << endl;
    dq.pop_front();
    cout << "After popping front, Front of Deque: " << dq.front() << endl;
    return 0;
}

Output:

Front of Deque: 10
Back of Deque: 30
After popping front, Front of Deque: 30

Explanation:

1. #include<deque>: This includes the header for the C++ standard library's deque.

2. std::deque<int> dq;: This is an instance of the STL deque for storing integers.

3. push_front(int item): This method adds an item to the front of the deque.

4. push_back(int item): This method adds an item to the rear of the deque.

5. pop_front(): This method removes the front item of the deque.

6. pop_back(): This method removes the rear item of the deque.

7. front(): This retrieves, but does not remove, the front item of the deque.

8. back(): This retrieves, but does not remove, the rear item of the deque.

9. main(): This function demonstrates the usage of our Deque. Items are added to both the front and back of the deque, and the output showcases how the deque allows for operations on both ends.