 Double-ended queue

A double-ended queue supports insertion and removal at both ends. It combines the access patterns of a stack and a queue without promising fast arbitrary indexing. For example, appending a,b at the right and then c at the left produces c,a,b; removing at the right returns b. A circular array or a doubly linked list can implement the abstraction, with different allocation and indexing costs. Python's deque provides approximately constant-time end operations, unlike repeatedly inserting at the start of an ordinary list.^[ref]