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.

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.

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.

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.

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.

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.

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

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.

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

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:

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

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.