Stacks and Queues: How These Fundamental Data Structures Work

Stacks and queues are two fundamental data structures used to organize, store, and process information in computer programs. Both hold collections of items, but they differ in the order in which items are added and removed. A stack follows last in, first out (LIFO), meaning the most recently added item is removed first. A queue follows first in, first out (FIFO), meaning the earliest added item is removed first.

These simple rules have important consequences for how software handles tasks, remembers actions, processes requests, and manages information. Stacks are useful when recent actions must be reversed or when a program needs to track nested operations. Queues are useful when items should be processed in the order they arrive.

Understanding how these structures work begins with their basic operations, but their practical value becomes clearer when we examine how they are implemented, how their performance differs, and why programs choose one over the other.

What a stack is and how it works

A stack is a collection in which items are added and removed from the same end, called the top. Because the newest item sits at the top, it is the first one available for removal.

Consider a stack of plates. When someone places a new plate on top, that plate becomes the easiest to reach. To remove a plate without disturbing the others, the person takes the top plate first. A computer stack follows the same principle, although its items may be numbers, text, objects, or other pieces of data rather than physical objects.

Suppose a program adds three values to an empty stack in this order: 10, 20, and 30. The top of the stack is now 30. Removing an item returns 30 first, followed by 20 and then 10. The removal order is the reverse of the insertion order.

A stack typically supports three core operations:

• Push: Add an item to the top of the stack.
• Pop: Remove and return the item at the top.
• Peek: Examine the top item without removing it.

A stack also needs a way to determine whether it contains any items. Attempting to remove an item from an empty stack is commonly called a stack underflow. A program can prevent this condition by checking whether the stack is empty before performing the removal.

The defining feature is not the type of data stored but the restriction on how it is accessed. A stack does not ordinarily let a program remove an arbitrary item from the middle through its standard operations. Items above that position must be removed first.

What a queue is and how it works

A queue is a collection in which items are added at one end and removed from the other. New items join the back, while the next item to be processed leaves from the front. This arrangement preserves the order in which items enter the queue.

A line of people waiting for service provides a familiar example. Someone who joins the end of the line generally waits until the people ahead have been served. A computer queue applies the same ordering principle to data and tasks.

Imagine a program placing three jobs into an empty queue: A, B, and C. Job A enters first, followed by B and C. When the program processes the queue, it removes A first, then B, and finally C. The items leave in the same order in which they arrived.

The main queue operations are:

• Enqueue: Add an item to the back of the queue.
• Dequeue: Remove and return the item at the front.
• Peek or front: Examine the next item to be removed without taking it out.

As with a stack, a queue needs an empty-state check. Attempting to remove an item from an empty queue can produce an underflow condition. Some implementations also impose a capacity limit, so adding an item to a full queue may fail or require the program to wait.

The distinction between a queue and a stack is therefore about access order. A queue preserves arrival order, while a stack reverses it. That difference determines which structure is appropriate for a particular problem.

How stacks and queues differ

Stacks and queues can store the same kinds of data and support similar basic operations, but their access rules make them suited to different tasks.

Suppose a program receives the values A, B, and C in that order. A stack removes C first, while a queue removes A first. The underlying data may be identical, but the order of access changes how the program behaves.

Neither structure is inherently better. A stack is appropriate when the latest item deserves attention first, particularly when a program must retrace recent steps. A queue is appropriate when older items should receive attention before newer ones.

The choice also depends on the surrounding system. A queue can preserve the order in which requests are accepted without guaranteeing that every request will finish in that order. Multiple workers, different processing times, cancellations, and scheduling rules can alter completion order. Similarly, a stack provides last-in, first-out behavior only when the program uses it according to its intended access rules.

How stacks and queues are implemented

A stack or queue describes a way of organizing and accessing data, not a single physical arrangement in computer memory. Programmers can implement either structure using different underlying representations. Two common choices are arrays and linked lists.

An array stores elements in indexed positions, typically in a contiguous region of memory for a conventional array implementation. Its positions can be accessed by index, which makes it efficient for managing ordered collections. A linked list, by contrast, consists of elements called nodes, each of which stores data and a reference to another node or to neighboring nodes.

The implementation matters because it affects memory use, performance, and the conditions under which an operation becomes expensive.

Implementing a stack with an array

An array-based stack can use an index to mark the current top item. When the program pushes an item, it places the item in the next available position and advances the top index. When it pops an item, it returns the value at the top and moves the index backward.

For example, if an array-based stack contains 10, 20, and 30, its top index identifies 30. Popping the stack returns 30 and adjusts the index so that 20 becomes the top.

With enough available capacity, both push and pop take constant time, written as O(1). This notation describes how an operation’s running time scales as the amount of data grows. Constant-time work does not increase proportionally with the number of stored elements.

Some array implementations have a fixed capacity. If the stack fills up, the program must reject new items or use another strategy. Dynamic arrays can grow by allocating a larger array and copying the existing elements when necessary. Most pushes remain constant-time operations, but a push that triggers this expansion takes longer. Across a long sequence of pushes, the average cost per operation can still be constant, a property known as amortized O(1) time.

Implementing a queue with an array

A straightforward array-based queue can track both the front and back positions. New items are written at the back, and removed items are read from the front.

However, an implementation that repeatedly shifts every remaining element toward the beginning after a dequeue can waste time. Removing the first item from a collection of nnn elements may require moving the other n−1n-1n−1 elements, making that operation O(n).

A more efficient design uses a circular queue, which treats the end of an array as connected to its beginning. Instead of shifting elements after a removal, the queue advances its front index. The back index also advances as items are added, wrapping around to the beginning when it reaches the end.

This arrangement allows enqueue and dequeue operations to take O(1) time when the queue has available capacity. A full circular queue must distinguish between occupied and available positions, often by tracking the number of stored elements or using an additional state convention. If the implementation supports dynamic growth, expanding the underlying array introduces occasional additional work.

Implementing stacks and queues with linked lists

A linked-list implementation stores each item in a node connected to other nodes through references. It does not require the elements to occupy adjacent memory positions.

A stack can use the head of a singly linked list as its top. Pushing an item creates a new node and connects it to the previous head. Popping removes the head and updates the reference to point to the next node. Both operations take O(1) time.

A queue can use a singly linked list with references to both the first and last nodes. Enqueuing adds a node at the tail, while dequeuing removes the head. Maintaining both references allows these operations to take O(1) time. When the last item is removed, the implementation must also update the tail reference to indicate that the queue is empty.

Linked lists can grow as new nodes are allocated, subject to available memory, but they require extra storage for references. They may also involve more memory allocations and less favorable cache behavior than array-based implementations. Arrays generally have lower per-element overhead and better locality, while linked lists can avoid resizing a large array. The better choice depends on the workload, memory constraints, and implementation details.

Why stacks are essential in computing

Stacks appear throughout software because many computations involve temporary states that must be completed or revisited in reverse order.

One of their most important uses is managing function calls. When a program calls a function, the computer needs to keep track of information such as where execution should resume, along with relevant local variables and other call-specific state. Many programming language implementations organize this information in call frames, which are commonly managed using a call stack.

If function A calls function B, and B calls function C, the most recent call is C. When C finishes, execution returns to B. When B finishes, execution returns to A. This reverse order of completion follows the stack’s LIFO rule.

Recursive functions make the relationship especially clear. Recursion occurs when a function calls itself, directly or indirectly. Each active call needs its own execution state. As the recursive calls accumulate, the call stack records them. When the deepest call finishes, the program unwinds the stack as the earlier calls resume and return.

If recursion becomes too deep, the program may exhaust the resources available for its call stack. This can produce a stack overflow, an error distinct from attempting to pop an empty stack. The exact limits and implementation details depend on the programming environment.

Stacks are also useful in expression evaluation. Consider a mathematical expression with nested parentheses. A program can use a stack to track opening parentheses and verify that closing parentheses match the most recent unmatched opening ones. If the program encounters an opening parenthesis, it pushes it onto the stack. When it encounters a closing parenthesis, it checks the top of the stack and removes the matching opening parenthesis. The expression is properly balanced only if every closing parenthesis has a match and no unmatched opening parentheses remain.

Compilers and interpreters use related techniques to process nested structures, evaluate expressions, and manage intermediate operations. Stacks also support depth-first search, a graph and tree traversal method that explores one path as far as possible before returning to earlier alternatives.

Another familiar application is undo functionality. An editor may place each reversible action on a stack. When a user selects Undo, the program removes the most recent action and reverses its effect. Some applications maintain separate stacks for undo and redo operations, moving actions between them as the user changes direction.

These examples share a common pattern: the program must deal with the most recent unfinished operation, nested state, or reversible action before returning to older ones.

Why queues are essential in computing

Queues are valuable when work arrives over time and needs to be handled in a defined order. They separate the arrival of tasks from their processing, allowing a system to accept work even when it cannot perform every task immediately.

An operating system or application may place pending tasks in a queue. A printer, for example, can accept several documents while printing them one at a time. The queue keeps track of documents awaiting service. The system may apply additional rules, such as priorities or cancellation, so its complete behavior can be more complex than a simple FIFO queue.

Queues also appear in networking and data processing. A producer creates or sends items, and a consumer processes them. A queue between the two can absorb temporary differences in their speeds. If incoming data arrives faster than it can be processed for a short period, the queue stores the excess work for later. This arrangement is known as buffering.

Buffering does not eliminate a persistent mismatch between production and processing rates. If items continue arriving faster than they can be consumed, the queue grows until it reaches a capacity limit or available memory is exhausted. A system must then apply a policy, such as slowing the producer, rejecting new items, or dropping selected data.

Queues are also important in graph algorithms. Breadth-first search explores a graph or tree level by level, visiting nearby nodes before moving farther away. It places newly discovered nodes in a queue and processes them in arrival order. In an unweighted graph, breadth-first search can find a shortest path measured by the number of edges, provided the search is carried out correctly from the starting node.

In asynchronous software, queues can hold events, messages, or requests that will be handled when the relevant component is ready. This helps different parts of a program operate at different times without requiring every action to happen immediately. In systems with multiple workers, however, a queue’s FIFO removal order does not necessarily determine the order in which tasks finish.

The common principle is that queues preserve pending work and provide a predictable rule for selecting what should be processed next.

How priority queues differ from ordinary queues

Not every system should process items strictly in arrival order. Some tasks are more urgent than others, and a data structure called a priority queue is designed to select items according to priority rather than ordinary FIFO order.

For example, a scheduling system may need to process a high-priority event before routine background work, even if the routine work arrived first. A priority queue supports that decision by removing the item with the highest or lowest priority, depending on its design.

A priority queue is often implemented using a heap, a tree-like structure that makes it efficient to access the item with the best priority. Other implementations are possible, and their performance differs.

Although its name includes the word queue, a priority queue does not follow the same ordering rule as a standard FIFO queue. If several items have equal priority, their relative order depends on the implementation. A priority queue can be useful for task scheduling, shortest-path algorithms, and event-driven simulations, where selecting the next item by importance or value is more useful than simply selecting the oldest one.

This distinction matters because choosing a data structure requires understanding the required behavior, not just recognizing a familiar name.

How to choose between a stack and a queue

The most useful question is what determines the next item a program should process.

Choose a stack when the most recently added item must be handled first. This is common in nested operations, backtracking, expression processing, and undo systems. Choose a queue when items should generally be handled in the order they arrive, as in basic task processing, buffering, and breadth-first search.

Performance is another consideration, but both structures can support their core operations in constant time with suitable implementations. The practical differences often come from memory allocation, resizing, access patterns, concurrency requirements, and whether the structure has a fixed capacity.

A program may also need something other than a basic stack or queue. If it must access arbitrary items efficiently, an array, hash table, tree, or another structure may be more suitable. If tasks have different levels of urgency, a priority queue may be the better fit. If the system must process data continuously while managing limited memory, the queue’s capacity and overflow policy become as important as its ordering rule.

Stacks and queues are fundamental because they impose simple, predictable rules on how data is accessed. Their power comes not from storing information in a special way, but from making the order of processing explicit. Once that order is understood, many common patterns in software—from returning through nested function calls to handling streams of incoming work—become easier to recognize and reason about.