Stacks, queues and deques

MIT’s 6.006 notes define these as special cases of a sequence: a stack only inserts and deletes at the end, a queue inserts at the end and deletes at the front. Any layout that makes those ends O(1) will do. A dynamic array is a fine stack, since append and pop at the end are amortized O(1). It is a poor queue: removing from the front shifts everything, so Python’s tutorial says lists “are not efficient for this purpose” and points to collections.deque, which appends and pops at either end in about O(1).

Deques avoid the shifting in one of two ways. Rust’s VecDeque is a growable ring buffer and Java’s ArrayDeque a resizable array, with most operations in amortized constant time. CPython’s deque is a doubly linked list of arrays, and C++’s std::deque typically uses a sequence of separately allocated fixed-size arrays, with O(1) random access and O(1) insertion at either end; the price is a large minimum footprint, since a std::deque holding one element allocates a whole block (for example 4096 bytes or 16 elements, whichever is larger, on 64-bit libc++).

Java’s docs say ArrayDeque is likely faster than Stack when used as a stack and faster than LinkedList when used as a queue, and recommend Deque over the old Stack class. C++’s std::stack is an adaptor over another container, std::deque by default. In Rust, Vec is the stack and VecDeque the queue; in Go a slice serves as a stack.