Specialized Linear Lists: Stacks, Queues, and Deques

Key Insight

Linear lists where insertions, deletions, and accesses primarily occur at one or both ends are frequently encountered and given special names. A stack is a linear list where all insertions and deletions (and typically all accesses) are restricted to one end, known as the 'top'. In a stack, the 'youngest' item—the one most recently inserted—is always removed, adhering to a Last-In-First-Out (LIFO) principle. Analogies include cafeteria plate stacks or railway switching networks, where items are 'pushed' onto the top and 'popped' off. Stacks are widely used in processing nested structures like programming languages, arithmetic expressions, and recursive algorithms.

In contrast, a queue is a linear list where all insertions occur at one end (the 'rear') and all deletions (and typically all accesses) happen at the other end (the 'front'). The 'oldest' item is always removed; nodes exit in the same order they entered, following a First-In-First-Out (FIFO) principle, similar to people waiting in line. While 'queue' can sometimes be used broadly, in this context, it specifically refers to this ordered FIFO discipline. Historical names for stacks include push-down lists, cellars, and LIFO lists, while queues were sometimes called circular stores or FIFO lists, reflecting their widespread importance and independent discovery; 'stack' and 'queue' are now standard terminology.

A deque, or 'double-ended queue', is a linear list that permits all insertions and deletions (and usually all accesses) at either end. This makes deques more general than both stacks and queues. Specialized variations include output-restricted deques (deletions from only one end) and input-restricted deques (insertions at only one end). Specific terminology is used when interacting with these structures: 'push' and 'pop' for stacks (referring to 'top' and 'bottom'); 'front' and 'rear' for queues (indicating removal and addition points); and 'left' and 'right' ends for deques. Notationally, `x ← A` removes the top/front element, and `A ← x` inserts it at the top/rear, with such operations being meaningless if the list is empty.