Home CPSC 340

Stacks

 

Overview

The next data structure we will look at is the stack. The data structures we have looked at thus far, arrays and linked lists, have been primarily concerned with how data is physically stored and accessed. Stacks, on the other hand, are primarily concerned with how data is logically stored and accessed. In fact, a stack can be built using either an array or a linked list as the base.

Logically, you can think of a stack as a bunch of things piled on top of each other. The only part of the stack that can be directly dealt with is the top. If you have a stack of papers, the only one you directly read is the top one. Likewise, if you have a stack of dinner plates, the only one you can directly put food on is the one on top.

A number of objects are 'stacked' on top pof each other, with an arrow pointing to the top object.
A stack of things

If you want to take something from the stack, you can only take the thing that is on top of the stack. The rest of the stack is totally inaccessible as long as the thing on top is there. Taking the top thing off of the stack is usually called "popping from" the stack. When we pop from the stack, we both read the top and remove it.

The 'pop' operation removes the top object from the stack
Popping from the stack removes the top item

Likewise, if you want to add something to the stack, you have to add it to the top. You can't insert at the bottom, or the middle, or any other place. Adding something to the top of a stack is called "pushing onto" the stack. Once that is done, the old top becomes buried and the thing we just pushed becomes the top.

The 'push' operation adds a new object to the top of the stack
Pushing onto the stack adds a new item on top

Stacks are sometimes called a "Last In First Out" or LIFO data structure because the last thing that was added is going to be the first one out.


 

Applications of Stacks

Stacks are so much more limited in terms of how they can be used than other data structures, that you might think they are of limited use. As it turns out, there are several problems that can be solved best with stacks:

And many more.


 

Implementing a Stack with an Array

We can use an array to implement a stack. In order to do this, we will create an array to hold all of the items in the stack and keep track of where the top is. If we have a stack of integers, implemented as an array, then we start with the array empty and set top to -1.

The array begins empty, with the top referring to -1 since there is no item
An empty array stack

Then when we push items onto the stack, we will increment the top and store our numbers there:

The array now contains four items, they are stored in the first four slots
of the array with the top storing the index of the rightmost item.
An array stack after pushing some data

To pop items off the stack, we will simply decrement the top. We don't really need to erase the numbers out of the array. Since we change the index stored as the top, the next time we try to push or pop, it will be like those numbers aren't there.

After popping items, we move the top index back to the left, leaving the
old items still there.
The array stack after popping some data

The following is an example of a simple array-based Stack class:


class Stack {
    private int top;
    private int[] array;

    public Stack(int size) {
        top = -1;
        array = new int[size];
    }

    public void push(int value) {
        array[top + 1] = value;
        top++;
    }

    public int pop() {
        top--;
        return array[top + 1];
    }

    public boolean empty() {
        return top == -1;
    }
}

 

Implementing a Stack with a Linked List

One drawback of using an array to implement a stack is that we can fill up the array. We don't handle this in the example above, but if we try to push on a stack that is full, we will write past the bounds of our array. To properly handle this case, we would need to allocate a new array and copy everything over.

In order to avoid that, we can store the stack inside of a linked list instead of an array. Because we only ever care about the top of the stack, a singly-linked list will suffice. When writing a stack with a linked list, we can change the terminology a little bit and rename the next pointer to "underneath" and the head of the list to "top":


    private class Node {
        public Type data;
        Node underneath;
    }

    Node top;

In an empty stack, the top node is equal to NULL. In a stack with nodes, we always keep a pointer to the top node, which has a pointer to the one underneath it and so on. The bottom of the stack has an underneath pointer of NULL:

The list stack contains a top variable pointing to the top node in
the stack.  Each node points to the one underneath it, with the last
pointing to null
A stack implemented as a linked list

When we push an item onto the stack, we are essentially adding at the front of the linked list. Likewise when we pop we are removing from the front of the linked list. Because stacks are more restrictive than an actual linked list, they are a bit simpler to program.

The following is an example of a simple list-based Stack class:


class Stack {
    private class Node {
        double data;
        Node underneath;
    }
    Node top;

    public Stack() {
        top = null;
    }

    public void push(double val) {
        Node newNode = new Node();
        newNode.data = val;
        newNode.underneath = top;
        top = newNode;
    }

    public double pop() {
        double value = top.data;
        top = top.underneath;
        return value;
    }

    public boolean empty() {
        return top == null;
    }
}

 

Reverse-Polish Notation

One application of stacks is in evaluating arithmetical expressions. We could write a program to evaluate usual arithmetical expressions (which would also involve a stack), but instead here we will evaluate Reverse Polish Notation (RPN) expressions.

RPN, also called postfix notation, is a system of writing mathematical expressions where the operator comes after the operands instead of in between. For example, we would normally write the seven plus two as:

7 + 2

In RPN, this would be written as:

7 2 +

We can combine multiple operations in RPN like so:

7 2 + 5 -

What this means is we apply + to 7 and 2 which gives us 9. Then we take the 9 and 5, then apply minus to those giving us 4. We can also have more than two numbers in a row:

1 2 3 4 + +

One big advantage of RPN is that we no longer need to use parenthesis to specify the order of operations. For example the infix operations:

(1 + 2) * 3

and:

1 + (2 * 3)

have different values. In RPN, the first one would be written as:

1 2 + 3 *

and the second would be:

1 2 3 * +

Another big advantage of RPN is that it can be more easily evaluated in a computer program. This is because we only need to scan left to right, instead of looking through the expression multiple times and following the order of precedence.

We can write a program to implement this task using a stack. To do this, we will scan through the RPN expression. Each time we see a number, we will push it onto the stack. When we see an operator we will pop two values off the stack, apply the operation to them, and push the result on the stack. At the end of the expression, the answer should be on top of the stack.

The following code implements this:


public class Calculator {
    public static void main(String args[]) {
        // create a stack for our values
        Stack<Double> stack = new Stack<Double>();

        // read the input and break it into words
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        String[] words = line.split(" ");

        for (String word: words) {
            try {
                // try to convert it to a double and push it
                double value = Double.parseDouble(word);
                stack.push(value);
            } catch (NumberFormatException e) {
                // handle the operators
                if (word.equals("+")) {
                    double a = stack.pop();
                    double b = stack.pop();
                    stack.push(a + b);
                } 
                else if (word.equals("*")) {
                    double a = stack.pop();
                    double b = stack.pop();
                    stack.push(a * b); 
                }
            }
        }

        // print the answer
        System.out.println(stack.pop());
    }
}

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.