Stacks are used all over in computer science, however most of the time their magic is happening in a less palpable view to the user than it's close relative, the queue. Perhaps in programming you might have come across an error labeled "Stack Overflow", which is when there are too many resources being utilized by a process than are available on the computer's "Stack". Stacks are also used in other places like computer caches where the most recently seen things are kept at the ready, while things that haven't been needed in a while might take a little longer to see again. As it turns out, stacks make for a very powerful data structure.

Assumptions

Knowledge of <a href="https://www.devmaking.com/learn/data-structures/linked-list/" target="_blank" style="color:inherit;">Linked Lists</a> and Arrays
Understanding of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" target="_blank" style="color:inherit;">Big-O Notation</a>

What is a Stack?

A Stack is a list of objects where each item is added and removed in Last-in First-out (LIFO) Order, similar to a stack of papers being put down and picked up one sheet at a time, the first sheet put down will be the last sheet picked up. A stack is often implemented using an Array or Linked List structure.

Understanding LIFO

Last-in, First-out, sometimes referred to synonymously as first-in, last-out (FILO), is a process where the most recent element added into a structure is always the first element removed from the structure.

Conceptualization

One of the simplest ways to imagine a stack is like a "stack" of papers placed on a desk. Suppose a professor at a university had a pile of exams mounting up on their desk as students finished them.

When the student's go up to turn in their exam, they place the packet on top of the now building stack of papers. To use terminology that will be seen later, we can say the students are "pushing" their exams on top of the stack of papers.

Now, our professor is very busy with publishing their research article and does not want to waste any time, so they pick up the exam on top of the stack of papers and begin grading it. As the professor is grading the paper, more students come by to push their exams on top of the stack. Again, to use terminology that will be seen soon, we will say the professor is "popping" exams off the top of the stack.

Upon finishing grading the first exam, the professor reaches for the next exam on top of the stack of papers, "popping" the top exam off the stack, and begins grading. This process continues until all the exams are graded.

When the professor is finished grading all the exams, they have a new stack of completed papers. However, if the order that students turned in their exam was taken note of and then the stack of graded exams was examined, it would appear to be all out of sorts, because the professor was popping papers off the top of the stack while other students were also pushing their exams onto the top of the stack.

> If the professor waited until all exams were pushed onto the stack before grading them, it would appear that the professor had graded them in reverse order, starting with the last exam submitted.

The actions of students pushing on top of the stack of papers and the professor popping an exam off the top of the stack mimics exactly the behavior of stacks in computer science.

Array Based Stacks vs. Linked List Based Stacks

Depending on what the requirements of the program are, a stack may have to be implemented as either an Array or a Linked List. Unlike queues, stacks are very easy to implement in arrays, where the last element inserted is removed, and no array shifts or rebuilds need to occur, aside from potentially expanding the stack.

For the purposes of this article, we will be going over a Linked List implementation of a stack. But before that, here are some times where you may want to prefer one implementation of a stack over another:

Array based Stack

When the maximum size of the stack is generally going to be static and unchanged throughout the use
When high performance is mandatory: allocating space once and accessing that memory is faster than allocating new memory each time a Linked List Stack node is pushed.
There is a very tight budget on memory: while a linked list stack increases memory only as more is needed which can give it an advantage early on, arrays store only one pointer for the entire array where linked lists store a pointer for each node, which can have a negative effect on memory usage in comparably sized stacks.

Linked List based Stack

When the maximum stack size is not known and may constantly change.
When memory is a concern, but not being budgeted to a T: while it was mentioned that arrays can be more efficient memory users by only needing a single pointer, an array based stack that can fit 128 elements will still use the space that 128 elements would take up even if the stack is empty. An empty linked list based stack takes up only the amount of memory that is currently needed.

Linked List Stack Composition

A stack is almost a subset of the common features found in regular linked lists. The Linked List operations addFirst, getFirst, removeFirst, and sizeOf encapsulate a majority of the features that can be found in stack implementations.

As it would follow, all we need is a head pointer to the top of the stack, and for ease of use a variable to track the current size of the stack.

The Node class of the stack will look identical to a basic linked list node as well:

/* pseudo-code */
class Node {
    int value;
    Node next;
}

Basic Stack Operations

Two operations, push and pop, govern a majority of the functionality needed to use a stack. As mentioned, we will be discussing these methods in a linked list implementation.

Push

Adding to the top of a stack, or pushing onto a stack, takes an element and places it in the front of the list. While mentioned that in an array implementation would add and remove from the last unused index, in a linked list implementation it is simpler to add and remove from the front of the list, requiring O(1) time to perform the operation.

This operation closely mimics a linked list's addFirst operation:

/* pseudo-code */
// Node that represents the top of the stack.
Node head;
// Keeps track of the size of the stack.
int size;

function push(int value){
    // Create a new node with the value provided.
    Node tmp = new Node(value);
    // Assign its next node to the current head of the stack.
    tmp.next = head;
    // Set the head to the new top of the stack.
    head = tmp;
    // Increment the size of the stack.
    size += 1;
}

Pop

Popping an element from the top of the stack is similar to performing the push operation, but in reverse. Taking note of the head node, we assign the head to the next element in the stack and return the previously first element's value. A word of warning though, if you pop off of an empty stack, most implementations will intentionally throw an exception. The poll method that will be covered ahead might be a useful alternative method to employ in the case that an exception being thrown is not desirable.

Just as push closely mimics a linked list's addFirst method, the pop method acts very similar to a linked list's removeFirst method, except that it returns the removed element's value:

/* pseudo-code */
Node head;
int size;

function pop() {
    if ( stack is empty ) {
        throw an exception;
    }
    // Take note of the current head.
    Node tmp = head;
    // Increment the head to the next node.
    head = head.next;
    // Decrement the size of the stack.
    size -= 1;
    // Return the popped node's value.
    return tmp.value;
}

Additional Stack Operations

The two methods discussed so far - push and pop - cover the general use cases when it comes to stacks. However, sometimes we'll need a few more tools at our disposal to properly tackle a problem. This is where additional functions such as peek, poll, isEmpty, and isFull come in handy. These methods allow us to do things such as check the next element of the stack without removing it, and attempt to remove from an empty stack without receiving an exception.

Peek

With only the push and pop methods, checking the next value of a stack without removing it would be cumbersome, but not impossible; we could simply pop the element off the stack, examine it, and then push it back into the stack. However, these operations are overkill compared to designing a new method that simply checks the value of the top element on the stack, and that method is peek.

This method allows the programmer to literally peek at the next item in the stack without removing it. To implement this with a linked list is as simple as returning the value of the head node:

/* pseudo-code */
Node head;

function peek(){
    if ( stack is empty ){
        throw an exception;
    }
    return head.value;
}

> notice that if the stack is empty, we throw an exception, just as we would if we tried to pop off of an empty stack.

Poll

Polling from a stack is for all intents and purposes the same as popping, except in the case that the stack is empty. When this is the case, the method returns null instead of throwing an exception. This can be preferable in some cases, however a majority of the use cases that poll covers can also be covered using a combination of isEmpty and pop.

/* pseudo-code */

function poll(){
    if ( stack is empty ){
        return null;
    }
    // you can call pop here,
    // or copy in the pop code.
    else return pop();
}

Is Empty

As mentioned above, using a combination of isEmpty and pop reduces the use cases of poll significantly. There are a few ways that isEmpty can be approached; the first is to check if the head node is null, the other is to check against the size of the stack. For this example, the size of the stack will be queried:

/* pseudo-code */
int size = 0;

function isEmpty(){
    Return size &lt;= 0;
    /* == can be confidently used instead
    if the other methods are correctly implemented*/
}

Is Full

In array based stacks especially, the isFull function can be vital to catch and/or avoid potential stack overflow exceptions. If your implementation of the stack data structure requires that you provide a maximum size, then the push function should also be refactored with an additional check whether the stack is full or not.

Provided that the max size of the stack and the current size are both specified, isFull is a simple comparison operation:

/* pseudo-code */
int maxSize = 10;
int size = 0;

function isFull(){
    Return size &gt;= maxSize;
    /* == can be dependably used here also,
    you should also hope that it's not true that 
    size is &gt; max size potentially!*/
}

When to use a Stack

Stacks have a wide variety of use cases across the domain of computer science, here are a few:

Reversing a list's order: if you were paying attention to the conceptualization example, the order that the professor removed the exams from the initial stack would have appeared to be in reverse order if the professor waited to grade the exams until all submissions had been made.
Undo and Redo commands: undoing a recent command, often used in OOP in conjunction with the command pattern, allows users to backtrack their steps. Upon popping an action out of the "undo" stack, that action is then pushed on top of the "redo" stack if the user decides to double back on their "undo".
Memory management: while used in a general purpose case for managing memory, in game engine programming more so, special versions of stacks called double ended stacks with front and tail pointers are utilized to allow for efficient resource management to keep memory utilization to a minimum and maintain game performance.
Syntax checking: in languages like C and Java, IDE's use stacks to find any errors with parenthesis or brackets being out of order by pushing the closing character into the stack and expecting it as the next "token".