Not Just A Linked List
Unlike `std::list`, `std::deque` is implemented as an array of fixed-size arrays (chunks). This means it supports O(1) random access via `dq[i]`, which a standard linked list cannot do.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
The C++ Standard Template Library implementation of a Deque. It provides highly efficient O(1) insertions and deletions at BOTH the front and the back.
Unlike `std::list`, `std::deque` is implemented as an array of fixed-size arrays (chunks). This means it supports O(1) random access via `dq[i]`, which a standard linked list cannot do.
The four most important methods are: push_front(x), push_back(x), pop_front(), and pop_back(). All of them run in amortized O(1) time.
Did you know? Both `std::stack` and `std::queue` in C++ actually use `std::deque` as their underlying container by default. The STL simply restricts the API to enforce LIFO or FIFO.