Queue and Stack Fundamentals

What You Need to Know First

You should be familiar with the following topics before continuing:

Core concepts of linked lists

Core concepts of arrays

We have already examined the two primary approaches computers use to organize data in memory: sequential storage via arrays and linked storage via linked lists. All of the data structures that follow are essentially specialized variations constructed on top of one of these two foundations.

The present discussion introduces the essential ideas behind queues and stacks. Subsequent articles will demonstrate concrete code implementations.

Begin with the underlying notion. Both queues and stacks are data structures that enforce restricted operations. The restriction arises because, relative to ordinary arrays and linked lists, the interfaces they expose are deliberately incomplete.

Recall the array and linked-list implementations covered earlier. Those structures furnish a complete set of insertion, deletion, search, and update operations, allowing an element at any valid index to be accessed or modified freely.

Queues and stacks impose stricter limits: a queue permits insertion only at one end and removal only at the opposite end; a stack permits both insertion and removal solely at a single end. In other words, they inherit the capabilities of arrays and linked lists but discard every operation that does not act exclusively on the boundary elements.

Visually, a queue accepts new elements only at the rear and releases elements only from the front, whereas a stack accepts and releases elements only at the top. The accompanying diagram orients the stack vertically and the queue horizontally simply for clarity. Internally, either structure can be realized with an array or a linked list, as later sections will illustrate.

A queue behaves like a waiting line at a ticket window: the earliest arrival is the first to depart, and the latest arrival is the last to depart. A stack resembles a stack of plates: the first plate placed becomes the bottom-most, the most recent plate rests on top, and plates are removed starting from the uppermost one.

Consequently, a queue is characterized as a first-in, first-out (FIFO) structure, while a stack is characterized as a last-in, first-out (LIFO) structure.

The fundamental operations exposed by each structure appear below.

# Core interface for a queue
class MyQueue:

    # Append an element to the rear of the queue; runs in constant time
    def push(self, e):
        pass

    # Remove the element at the front of the queue; runs in constant time
    def pop(self):
        pass

    # Inspect the element at the front of the queue without removing it; runs in constant time
    def peek(self):
        pass

    # Report the current number of elements; runs in constant time
    def size(self):
        pass

# Core interface for a stack
class MyStack:
    
    # Place an element onto the top of the stack; runs in constant time
    def push(self, e):
        pass
    
    # Remove the element from the top of the stack; runs in constant time
    def pop(self):
        pass
    
    # Inspect the element at the top of the stack without removing it; runs in constant time
    def peek(self):
        pass
    
    # Report the current number of elements; runs in constant time
    def size(self):
        pass

Exact method names differ from language to language, yet the semantics of each operation remain identical.

Certain language standard libraries omit native queue or stack types; in those cases the same behavior can be obtained by wrapping an array or a linked list. The following chapter begins by constructing both structures with linked lists.