Stack | Ucode

Appearance

On this page

Stack ​

A Stack is a data structure that follows the Last In First Out (LIFO) principle.

What is LIFO? Let’s first review the characteristics of a Queue, which follows the First In First Out (FIFO) principle:

           ────────────────────────
  (\(\       (\(\    (\(\    (\(\       (\(\
 (='.') ──▶ (='.')  (='.')  (='.') ──▶ (='.')
O(_")")    O(_")") O(_")") O(_")")    O(_")")
           ────────────────────────

In FIFO, the element that enters the queue first will also be the first to leave. Conversely, in LIFO, the last element added to the stack will be the first one to be removed. How do we achieve this? By sealing one end of the queue:

            ───────────────────────────────┐
  (\(\        (\(\    (\(\    (\(\    (\(\ │
 (='.') ◀──▶ (='.')  (='.')  (='.')  (='.')│
O(_")")     O(_")") O(_")") O(_")") O(_")")│
            ───────────────────────────────┘

Thus, a Stack is a data structure where elements can only be pushed onto the stack (push) and the last element added must be the first one to be popped off (pop):

Stack Operations ​

A stack has only two main operations:

  • Push an element onto the stack: push(E).
  • Pop the top element off the stack: pop().
  • Peek at the top element without removing it: peek().

In Java, we can implement the functionality of a stack using Deque:

  • Push an element onto the stack: push(E) / addFirst(E).
  • Pop the top element off the stack: pop() / removeFirst().
  • Peek at the top element without removing it: peek() / peekFirst().

Why doesn’t Java’s collections framework provide a separate Stack interface? Because there is a legacy class named Stack. For compatibility reasons, we cannot create a new Stack interface, so we have to "simulate" a stack using the Deque interface.

When using Deque as a stack, it's important to only call push(), pop(), and peek() methods and not addFirst(), removeFirst(), or peekFirst(), as this will make the code clearer.

Uses of Stack ​

Stacks are widely used in computing. For instance, the JVM maintains the hierarchy of method calls using a stack data structure when processing Java method calls. For example:

java
static void main(String[] args) {
    foo(123);
}

static String foo(int x) {
    return "F-" + bar(x + 1);
}

static int bar(int x) {
    return x << 2;
}

The JVM creates a method call stack. Each time a method is called, the parameters are pushed onto the stack, and the corresponding method is executed. When the method returns, the return value is pushed onto the stack, and the calling method retrieves the return value via a pop operation.

Since the method call stack has a capacity limit, too many nested calls can lead to a stack overflow, resulting in a StackOverflowError:

java
// Test for infinite recursive calls
public class Main {
    public static void main(String[] args) {
        increase(1);
    }

    static int increase(int x) {
        return increase(x) + 1;
    }
}

Let’s look at another use of a stack: converting integers between number bases.

For instance, how do we convert the integer 12500 to its hexadecimal string representation?

First, we prepare an empty stack:

│   │
│   │
│   │
│   │
│   │
└───┘

Next, we calculate (12500 ÷ 16 = 781) with a remainder of 4, and we push the remainder 4 onto the stack:

│   │
│   │
│   │
│   │
│ 4 │
└───┘

Then we calculate (781 ÷ 16 = 48) with a remainder of 13 (which is represented as 'D' in hexadecimal) and push 'D' onto the stack:

│   │
│   │
│ D │
│ 4 │
└───┘

Next, we calculate (48 ÷ 16 = 3) with a remainder of 0 and push 0 onto the stack:

│   │
│   │
│ 0 │
│ D │
│ 4 │
└───┘

Finally, we calculate (3 ÷ 16 = 0) with a remainder of 3 and push 3 onto the stack:

│   │
│ 3 │
│ 0 │
│ D │
│ 4 │
└───┘

When the quotient is 0, the calculation ends. We then pop all the elements off the stack to form the string "30D4", which is the hexadecimal representation of the decimal integer 12500.

Evaluating Infix Expressions ​

In programming, the mathematical expressions we use with parentheses are called infix expressions, where the operators are in the middle, for example: 1 + 2 * (9 - 5).

However, when a computer evaluates expressions, it cannot directly compute infix expressions. Instead, the compiler converts infix expressions into postfix expressions, such as 1 2 9 5 - * +.

The compilation process uses a stack. Let's skip the compilation step (which involves operator precedence and is more complex) and see how to compute a postfix expression using a stack.

Calculating a postfix expression does not consider precedence; we simply compute from left to right. First, we prepare an empty stack:

│   │
│   │
│   │
│   │
│   │
└───┘

Next, we scan the postfix expression 1 2 9 5 - * +. When we encounter the number 1, we push it onto the stack:

│   │
│   │
│   │
│   │
│ 1 │
└───┘

Next, we encounter the numbers 2, 9, and 5, and we push them onto the stack:

│   │
│ 5 │
│ 9 │
│ 2 │
│ 1 │
└───┘

When we encounter the minus sign, we pop the top two elements from the stack, calculate (9 - 5 = 4), and push the result 4 onto the stack:

│   │
│   │
│ 4 │
│ 2 │
│ 1 │
└───┘

Next, when we encounter the multiplication sign, we pop the top two elements from the stack, calculate (2 * 4 = 8), and push the result 8 onto the stack:

│   │
│   │
│ 8 │
│ 1 │
└───┘

Finally, when we encounter the plus sign, we pop the top two elements from the stack, calculate (1 + 8 = 9), and push the result 9 onto the stack:

│   │
│   │
│   │
│ 9 │
└───┘

After scanning, there are no more calculations to perform, so we pop the only element off the stack, resulting in a final value of 9.

Exercises ​

Please use a stack to convert a given integer to hexadecimal:

java
// Convert to hexadecimal
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String hex = toHex(12500);
        if (hex.equalsIgnoreCase("30D4")) {
            System.out.println("Test passed");
        } else {
            System.out.println("Test failed");
        }
    }

    static String toHex(int n) {
        return "";
    }
}

Advanced Exercise:

Use a stack to compile a string infix expression into a postfix expression, then execute the postfix expression to obtain the calculation result:

java
// Advanced exercise, choose carefully!
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String exp = "1 + 2 * (9 - 5)";
        SuffixExpression se = compile(exp);
        int result = se.execute();
        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String exp) {
        // TODO:
        return new SuffixExpression();
    }
}

class SuffixExpression {
    int execute() {
        // TODO:
        return 0;
    }
}

Advanced Exercise 2:

Compile an infix expression with variables into a postfix expression, passing the variable values when executing the postfix expression to get the calculation result:

java
// Super advanced exercise, choose

 carefully!
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String exp = "x + 2 * (y - 5)";
        SuffixExpression se = compile(exp);
        Map<String, Integer> env = Map.of("x", 1, "y", 9);
        int result = se.execute(env);
        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String exp) {
        // TODO:
        return new SuffixExpression();
    }
}

class SuffixExpression {
    int execute(Map<String, Integer> env) {
        // TODO:
        return 0;
    }
}

Conclusion ​

A Stack is a Last In First Out (LIFO) data structure. The methods for operating on stack elements are:

  • Push an element onto the stack: push(E).
  • Pop the top element off the stack: pop(E).
  • Peek at the top element without removing it: peek(E).

In Java, we can implement the functionality of a stack using Deque. It's important to only call push(), pop(), and peek() methods to avoid invoking other methods of Deque; also, avoid using the legacy Stack class.