Stack (Last-In-First-Out)

The stack, aka Last-In-First-Out (LIFO) list or pushdown store, data structure is surprisingly simple yet equally useful. Their primary purpose is to track a linear list of items in last-in-first-out order. As an example, consider a spring loaded stack of plates in a restaurant buffet line1. The last plate placed on top of the stack is the first plate removed and it’s not possible to remove a plate on the bottom without first removing the plates above it. Likewise, consider browser history: each new address is added to a stack. Pressing the back button removes the newest item from the stack and returns it.

History

The stack concept was employed in many forms long before it had a explicit name. For example, its use in accounting dates back to the 1800s2. As applied to computation, the exact origin is difficult to pinpoint. In 1947, Alan Turing described a stack like construct with bury and unbury operations. The earliest known fully formed representation was in a 1959 paper entitled Report on a General Problem-Solving Program by Newell, Shaw, and Simon3. The paper outlined a LIFO structure required to formulate pushdown automata which was a milestone in theoretical computation. However, its use is not sequestered to theory.

Edsger Dijkstra coined the term stack to denote LIFO data in his 1960 paper entitled Recursive Programming4. He used stacks to implement recursion in his Algol 60 compiler. The term caught on and is presently ubiquitous. Stacks are quite possibly the most common data structure in use today.

Stacks have three primary operations: push, pop, and peek5. They are outlined in the Pseudo Code section, take a minute to read them over. The image below depicts stack operations graphically.

stack operations

To solidify the concept, consider a stack of character data. The image below depicts a series of operations.

stack

Common Exceptions

No discussion of stacks is complete without mentioning the most popular programming exception ever conceived6: stack overflow. An overflow occurs when a push operation exceeds the memory available to a stack data structure. Suppose you have a stack data structure that is only capable of holding five items. In this case, six successive push operations will yield a stack overflow. At the other end of the spectrum is stack underflow. This exception occurs when attempting a pop or peek operation on an empty stack.

Certain stack implementations are more prone to stack overflows than others7. Stated differently, some implementations are constrained by a fixed sized while others are not8. Regardless, underflow is always a possibility. It’s common to create an is_empty operation to aid in overflow prevention. If is_empty returns true, the consumer knows that a pop will throw an underflow exception.

It’s wise to incorporate these well-known exception types into your own designs. The verbiage will be immediately recognizable by most seasoned programmers. This is something to keep in mind while completing the exercises.

Applications

  • Memory Management: Operating systems use a stack for managing memory.
  • Syntax Parsing: Compilers use stacks for expression parsing.
  • Backtracking: Keep track of tasks so they can be undone if necessary. Think of what happens when you press ctrl+z while using MS Word, or u when using VIM.
  • Graph Depth First Search

Pseudo Code

\begin{algorithm}
\caption{Stack Abstract Interface}
\begin{algorithmic}
\REQUIRE value = value to add to the stack
\FUNCTION{push}{value}
    \STATE add value to top of STACK
\ENDFUNCTION
\FUNCTION{pop}{}
    \STATE value $\gets$ top of STACK
    \STATE STACK $\gets$ STACK - value
    \RETURN value
\ENDFUNCTION
\FUNCTION{peek}{}
    \RETURN value at top of stack
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Implementation Details

A Linked List is an ideal data structure for implementing a stack. However, an Array is also a viable option.

Asymptotic Complexity

  • Push: $O(1)$
  • Pop: $O(1)$
  • Peek: $O(1)$

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions

Exercises

  1. Consult the supplied Pseudo Code to answer this question. With the assumption that you are starting with a well formed empty stack capable of tracking integer values, list the items that exist on the stack after the following operations:
    a. push(55); push(45); peek(); pop(); push(65);
    b. push(1); push(3); push(8);
    c. push(75); push(85); pop(); peek();
    d. push(100); peek(); pop(); push(200); pop(); pop();

    Answers (click to expand)
    1. 65
      55
    2. 8
      3
      1
    3. 75
    4. Stack Underflow
  2. Specify detailed pseudo code for a stack implementation using a:
    a. Fixed length array.
    b. Linked list.

    For formatting purposes, the answers to question 2 are located here.

  3. Using the programming language of your choice, write a program that accepts a random list of integers, stores them on a stack, and prints them in the reverse order that they were received.

  1. No discussion of stacks is complete without the plate analogy. The stack operations push and pop (introduced shortly) are named such because when you add a plate to the stack it pushes it down and when you remove one it pops up. 

  2. See the online article History of LIFO for a fascinating historical account. 

  3. Available online at https://exhibits.stanford.edu/feigenbaum/catalog/sy501xd1313 

  4. Published in Numerische Mathematik Volume 2, December, 1960 - Available online at https://link.springer.com/article/10.1007/BF01386232 

  5. It’s common to encounter additional operations. These three represent the minimal viable interface. 

  6. This assertion is based on nothing other than the author’s general impression of the popularity of error messages. One could definitely argue that null reference errors deserve the title. The truth is that exact statistics aren’t germane to the point at hand. If you’re feeling particularly pedantic, feel free to label this as sensationalism aimed at forcing the concept into the reader’s memory. 

  7. The exercises on this page ask the reader to implement a stack using both an array and a linked list. For bonus points, can you determine which of the two is more prone to overflow errors? 

  8. It goes without saying that all implementations are constrained by the total amount of memory available on a machine.