Stacks

Where you see LIFO

Here are three everyday places where the newest item comes out first:

Two more uses, which you will meet in later lessons:

Undo and Back are illustrations of the rule, not a description of how any particular app is programmed.

The whole program

Here is everything in one runnable file. main does the same calls as the walkthrough, except the last push(8). To see the overflow exception, add s.push(8); at the end of main.

 1public class Main {
 2  public static void main(String[] args) {
 3    ArrayStack s = new ArrayStack(3);
 4    s.push(4);
 5    s.push(9);
 6    System.out.println(s.pop());     // 9
 7    System.out.println(s.peek());    // 4
 8    s.push(2);
 9    s.push(7);
10    System.out.println(s.size());    // 3
11    System.out.println(s.isFull());  // true
12  }
13}
14
15class ArrayStack {
16  int[] data;    // cells that hold the stack items
17  int top;       // index of the top item; -1 means empty
18
19  ArrayStack(int capacity) {
20    data = new int[capacity];
21    top = -1;
22  }
23  boolean isEmpty() {
24    return top == -1;
25  }
26  boolean isFull() {
27    return top == data.length - 1;
28  }
29  int size() {
30    return top + 1;
31  }
32  void push(int value) {
33    if (isFull()) {
34      throw new IllegalStateException("Stack overflow: full.");
35    }
36    top++;
37    data[top] = value;
38  }
39  int pop() {
40    if (isEmpty()) {
41      throw new IllegalStateException("Stack underflow: empty.");
42    }
43    int value = data[top];
44    top--;
45    return value;
46  }
47  int peek() {
48    if (isEmpty()) {
49      throw new IllegalStateException("Stack underflow: empty.");
50    }
51    return data[top];
52  }
53}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Java's own stack: Stack<Integer>

Java has no ArrayStack, but it does come with ready-made stack classes, so real programs seldom write their own. The oldest is java.util.Stack, and exams often ask you to trace it. It has the same five methods as our ArrayStack: push, pop, peek, isEmpty, and size. Here is a short program that uses it:

 1import java.util.Stack;
 2
 3public class Main {
 4  public static void main(String[] args) {
 5    Stack<Integer> stack = new Stack<>();
 6    stack.push(10);
 7    stack.push(20);
 8    stack.push(30);
 9    System.out.println(stack.peek());
10    System.out.println(stack.pop());
11    System.out.println(stack.size());
12    System.out.println(stack);
13    stack.pop();
14    System.out.println(stack.isEmpty());
15    System.out.println(stack.pop());
16    System.out.println(stack.isEmpty());
17  }
18}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Two lines are new. This table shows how to read them aloud:

Now trace the program in a table, the same way as Part 3. Try it on paper first, then check:

30
30
2
[10, 20]
false
10
true

The newer choice: ArrayDeque

Stack dates from the first version of Java, and it has extra methods that break the stack rule (for example, get(0) reads the bottom item). Java's documentation says to use a deque ("deck," a double-ended queue) instead, such as ArrayDeque, which is also usually faster. It has the same push, pop, and peek:

 1import java.util.ArrayDeque;
 2
 3public class Main {
 4  public static void main(String[] args) {
 5    ArrayDeque<Integer> stack = new ArrayDeque<>();
 6    stack.push(10);
 7    stack.push(20);
 8    stack.push(30);
 9    System.out.println(stack.pop());    // 30
10    System.out.println(stack.peek());   // 20
11    System.out.println(stack);          // [20, 10]  top first!
12  }
13}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

The three stacks side by side:

All three are the same stack ADT: the same LIFO rule and the same methods, kept in different ways. In this course you still write your own, so you can see what happens inside.