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:

Evaluating arithmetic expressions.
Reversing things.
Checking for mismatched parenthesis.
Keeping track of where you are in a maze.
Implementing compilers and interpreters.

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;
    }
}