Prev Next

C++ Deque

A deque (double-ended queue) is a versatile container in C++ that allows insertion and deletion of elements from both the front and the back. It is part of the Standard Template Library (STL) and provides a dynamic array-like structure that can grow or shrink as needed.

Key Topics

Overview of Deques

Deques provide several advantages:

  • Efficient access to both ends of the container.
  • Dynamic resizing to accommodate varying numbers of elements.
  • Useful for implementing both queues and stacks.

Declaring Deques

To declare a deque, include the deque header and use the following syntax:

#include 
deque myDeque;

Common Deque Operations

Here are some common operations you can perform on deques:

  • push_front(): Adds an element to the front of the deque.
  • push_back(): Adds an element to the back of the deque.
  • pop_front(): Removes the front element from the deque.
  • pop_back(): Removes the back element from the deque.
  • front(): Returns the front element of the deque without removing it.
  • back(): Returns the last element of the deque without removing it.
  • empty(): Checks if the deque is empty.
  • size(): Returns the number of elements in the deque.

Example: Basic Deque Operations

#include 
#include 
using namespace std;

int main() {
    deque myDeque;
    myDeque.push_back(10);
    myDeque.push_front(20);
    myDeque.push_back(30);
    cout << "Front element: " << myDeque.front() << endl;
    cout << "Back element: " << myDeque.back() << endl;
    myDeque.pop_front();
    cout << "Front element after pop: " << myDeque.front() << endl;
    cout << "Deque size: " << myDeque.size() << endl;
    return 0;
}

Output:

Front element: 20 Back element: 30 Front element after pop: 10 Deque size: 2

Iterating Over Deques

Deques can be iterated using iterators, similar to vectors and lists. You can use a range-based for loop or standard iterators to access elements in a deque.

Example: Iterating Over a Deque

#include 
#include 
using namespace std;

int main() {
    deque myDeque = {10, 20, 30, 40, 50};
    cout << "Deque elements: ";
    for (int element : myDeque) {
        cout << element << " ";
    }
    cout << endl;
    return 0;
}

Output:

Deque elements: 10 20 30 40 50

Exercises with Deques

Here are some exercises to practice your understanding of deques:

  • Implement a program that simulates a playlist where you can add and remove songs from both ends.
  • Write a function that reverses the elements of a deque.
  • Simulate a browser's back and forward navigation using a deque.

Key Takeaways

  • Deques are double-ended queues that allow efficient insertion and deletion from both ends.
  • Common operations include pushing and popping elements from the front and back, as well as accessing the front and back elements.
  • Deques are versatile and can be used in various applications, including implementing queues, stacks, and more complex data structures.
  • Iterating over deques can be done using iterators or range-based for loops.
Prev Next