Chapter 7: Stacks

7.1The stack ADT

A data structure can be described at two levels. The first says what it does: which operations exist, what each changes and returns. The second says how: how the data is laid out in memory and what steps each operation takes. A first-level description is an abstract data type (ADT). This section treats the stack as an ADT; implementation comes next.

7.1.1What is a stack?

Picture a pile of clean plates. A washed plate always goes on top, and you take plates from the top. To reach the bottom one you must lift off every plate above it. Nobody pulls a plate from the middle; it is awkward, and the pile falls over.

A stack imitates this arrangement. Items are kept in sequence, but only one end, the top, is accessible, and both insertion and removal happen there. The item that comes off is therefore always the most recently added one still on the stack.

Push 1, 2, 3 and then pop three times, and you get 3, 2, 1: the last in came out first (LIFO), the first in came out last (FILO).

The discipline turns up all over software:

• Undo: A text editor pushes every change onto a stack. “Undo” reverses the latest change, then the one before, so changes are undone in reverse order.
• The browser’s “back” button: Visited pages sit on a stack, and “back” returns to the page you left last. Section 7.3.2 develops this with two stacks.
• Function calls: If main calls f and f calls g, then g finishes first, then f, then main. Languages therefore track calls on a stack (7.3.3).

Each case is about the most recently started job that has not finished. When it ends, we return to the job started just before it, and a stack keeps this list of waiting jobs as cheaply as possible.

7.1.2Basic operations

Five operations define the stack ADT. Their names are standard and match the Java library: push adds an item on top, pop removes the top item.

Only push and pop change the stack, adding or removing one item; the other three only report. top() and pop() both return the top item, but top() leaves it in place. When you must look at an item before deciding whether to remove it (as in the next greater element problem, 7.3.9), call top() and then pop().

On an empty stack there is no top item, so pop() and top() have nothing to return. Popping an empty stack is an error called underflow. Pushing onto a full stack of limited capacity is called overflow, which can only happen to bounded stacks (7.2.1).

7.1.3push and pop, step by step

Starting from an empty stack, we apply push(10), push(15), push(20), top(), and four pop() calls.

The table in Figure 7.1 is a handy layout for stack exercises: one row per operation, with its return value and the size afterward. Writing down the stack itself, bottom to top, at each step keeps you from popping the wrong item.

7.1.4A Java interface: separating the ADT from its implementation

In Java an ADT is naturally expressed as an interface, which lists the methods a class must provide without giving their bodies. For the stack:

public interface Stack<E> {
  int size();
  boolean isEmpty();
  void push(E e);
  E top();    // null if empty
  E pop();    // exception if empty
}

The <E> makes the stack generic. E is a type parameter: write Stack<Integer> for integers or Stack<Character> for characters, and E stands for that type throughout, so one piece of code serves every item type. The methods are those of Table 7.1, and the comments make empty-stack behavior part of the contract: top() returns null, while pop() throws an exception.

The interface separates “what” from “how”:

• The ADT answers “what?” It names the operations and their meaning and says nothing about arrays or linked lists.
• The implementation answers “how?” A class such as ArrayStack<E> implements Stack<E> writes each method for one storage scheme; a linked-list class can implement the same interface.
• Code written against the interface can swap implementations. A method taking a Stack<Integer> accepts an array-based or a linked stack without a line of the caller changing.

This matters in practice: if measurements call for a faster implementation, the interface keeps the change local.

Empty-stack behavior, however, differs between libraries:

Because of the differences in Table 7.2, always check isEmpty() before calling pop() or peek(). Otherwise the same code throws with one library and silently gets null with another, and the bug surfaces much later, where it is hard to trace.

7.1.5Algorithms for the operations

Before implementing, we write the operations in language-neutral pseudocode. Assume the stack lives in an array, along with an integer top holding the index of the top item. Indices start at 0, so the first item goes into cell 0, and an empty stack is represented by top = −1.

push(x):

begin
  if the stack is full   // top = cap−1
    error: overflow
  else
    increment top by 1
    stack[top] ← x
end

With capacity cap, the last valid index is cap − 1; once top reaches it, the array is full and a push overflows. Otherwise top is incremented and x is written into the new top cell. The order matters: done the other way round, x would overwrite the current top item.

pop():

begin
  if the stack is empty  // top = −1
    error: underflow
  else
    x ← stack[top]; decrement top by 1
    return x
end

If top = −1, we have underflow. Otherwise the top item is saved, top is decremented, and the saved item is returned; again, read first, then decrement.

top():

begin
  if the stack is empty return null
  else return stack[top]
end

isEmpty() and size():

isEmpty: true if top = −1, else false
size:    return top + 1

Why top + 1? The items occupy indices 0 through top, which is top + 1 indices. A three-item stack uses cells 0, 1, 2, so top = 2 and size = 3; an empty stack has top = −1 and size = 0.

7.1.6Time and space cost

The stack’s great strength is that all its basic operations take constant time. An operation whose running time does not depend on the number of items takes O(1) time. Table 7.3 gives the costs and their reasons.

The pseudocode of 7.1.5 shows why. Each operation does at most one comparison, one index update, and one array access, and accessing a known index takes the same time whatever the array’s size. There are no loops; nothing is shifted or scanned. A push onto a million-item stack takes as many steps as onto a three-item one.

Searching is different. The ADT’s only way to find a value is to pop items from the top and look at each. In the worst case (the value is at the bottom or absent) all n items come off: O(n). If you search often, a stack is the wrong structure.

A stack of n items must store them all, so it uses O(n) memory, while each operation needs only a few local variables: O(1) extra space.

There is one exception. In a stack built on a dynamic array, which grows when full, the push that triggers growth copies every item into a new array and takes O(n). Growth is rare, so the average cost per push over a long sequence is still constant, or amortized O(1); Section 7.2.6 works it out.

The speed comes from the restriction itself: with access limited to the top, no operation ever shifts or searches. A list that allows insertion in the middle or reading any index is more flexible, but pays with operations that take O(n).

7.2Implementation

To implement an ADT is to write it as a class built on a particular storage scheme. For a stack there are two basic options, an array or a list of linked nodes. This section codes both and compares them.

7.2.1Fixed-size and dynamic-size stacks

First decide how many items the stack can hold; the two answers give two kinds of stack.

A fixed-size stack sets its capacity at creation and never grows or shrinks; underneath is a fixed-length array. Pushing onto a full stack is an overflow error, popping an empty one an underflow error.

A dynamic-size stack grows and shrinks at run time. When full it raises its own capacity, say by doubling, and when the item count falls far below capacity it may shrink to return memory. It is built on a dynamic array or a linked list.

The two differ only when full. A dynamic stack can grow, but popping an empty one is still meaningless, so overflow occurs only in a fixed-size stack while underflow can occur in any.

7.2.2Two ways to implement a stack

The stack ADT can be implemented with an array or a linked list. Figure 7.3 shows the same stack (10, 15, 20 bottom to top) both ways.

In the array-based stack, push increments top and writes the item into arr[top]; pop takes arr[top] and decrements top. The bottom is always cell 0, and the stack grows toward the end of the array.

In the linked stack, the top is the list’s head: push inserts a node there, and pop removes it and returns its value. The pictures differ, yet as ADTs the stacks are identical: both have 20 on top, and a pop returns 20 from either.

7.2.3The array-based stack

An array-based stack whose capacity is fixed at creation is also called a bounded stack. Figure 7.4 shows three items (5, 8, 3) in an array of capacity 8.

Its advantages:

• Simplicity. An array and an integer suffice; the code is a few lines.
• Memory economy. Only the items are stored, with no per-node reference as in a linked list.
• Strict memory control. The stack can never take more than its capacity, a safeguard against malicious input that tries to grow a stack until memory runs out.
• Cache friendliness. The items occupy consecutive cells, and since the processor reads memory in blocks, consecutive data is faster to reach than scattered nodes. The same O(1) operations thus usually run faster in practice.

Points to watch:

• Check for fullness before pushing; otherwise the write falls outside the array and Java throws ArrayIndexOutOfBoundsException.
• Capacity is a compromise: too small and the stack overflows, too large and idle cells waste memory.
• In an array of objects, set each vacated cell to null, or the array keeps the removed object alive in memory for nothing.

7.2.4Code: ArrayStack

This class implements the Stack<E> interface of 7.1.4 with a fixed-capacity array.

public class ArrayStack<E> implements Stack<E> {
    private E[] data;
    private int top = -1;                    // -1 → empty stack
    public ArrayStack(int capacity) { data = (E[]) new Object[capacity]; }
    public boolean isEmpty() { return top == -1; }
    public int size()        { return top + 1; }
    public E top()           { return isEmpty() ? null : data[top]; }
    public void push(E x) {
        if (top == data.length - 1) throw new IllegalStateException("Overflow");
        data[++top] = x;
    }
    public E pop() {
        if (isEmpty()) throw new IllegalStateException("Underflow");
        E x = data[top];
        data[top--] = null;                  // drop the reference
        return x;
    }
}

How it works:

• data holds the items; top, the index of the top item, starts at -1 because a new stack is empty.
• The constructor allocates the array. Java forbids new E[capacity], because the type parameter E is unknown at run time, so we create an Object array and cast it with (E[]). The compiler warns that the cast is “unchecked”; it is safe as long as the array never leaves the class.
• isEmpty() tests top == -1; size() returns top + 1 (7.1.5).
• top() returns null for an empty stack, else data[top]. The conditional operator ? : yields its first value if the condition holds, its second otherwise. The class has both a field top and a method top(); Java tells them apart by the parentheses.
• push(x) throws IllegalStateException("Overflow") if top == data.length - 1, meaning the last cell is taken. Otherwise data[++top] = x; runs. ++top is a pre-increment: top rises first, and the new value serves as the index, fitting “increment, then write” (7.1.5) on one line.
• pop() throws an “Underflow” exception on an empty stack. Otherwise it saves the top item in x. In data[top--] = null;, top-- is a post-decrement: the old top is used as the index and that cell set to null, and then top drops by one. Finally x is returned.

++top versus top++ is decisive: data[top++] = x would overwrite the current top item, and data[--top] = null would clear the cell below the top.

No method loops, so each runs in O(1) time. The array has one cell per unit of capacity: O(capacity) space.

7.2.5Code trace: ArrayStack

We trace a stack of capacity 4 as main calls s.push(10), s.push(15), s.push(20), s.top(), s.pop(), s.push(25), s.push(30), s.push(40). The method bodies involved:

public void push(E x) {
  if (top == data.length - 1)
    throw new IllegalStateException("Overflow");
  data[++top] = x;
}
public E pop() {
  if (isEmpty())
    throw new IllegalStateException("Underflow");
  E x = data[top];
  data[top--] = null;          // drop the reference
  return x;
}
public E top() { return isEmpty() ? null : data[top]; }

On the first push(10), top = −1 differs from data.length − 1 = 3, so data[++top] = x raises top to 0 and writes data[0] = 10, one assignment regardless of array size.

top() returns data[2] = 20, changing nothing. The following pop() finds top = 2 ≠ −1, saves x = data[2] = 20, clears cell 2 with data[top--] = null, and lowers top to 1. It returns 20: last in, first out.

push(25) reuses cell 2, and push(30) fills the last cell, so top = 3. At push(40) the check yields 3 == 3: the array is full, IllegalStateException("Overflow") is thrown, and the array and top stay as they were. That is overflow in a fixed-capacity stack; a dynamic array would grow here instead.

In frames (c) and (d) of Figure 7.5, cell 2 holds 20, becomes null after the pop, and is refilled with 25. An array-based stack reuses its cells; removing an item never shifts the rest.

7.2.6Dynamic arrays: doubling when full

A fixed capacity fails when the number of items is unknown in advance. The remedy is to move the items to a bigger array when the current one fills; since a Java array cannot change length, “growing” means creating a new array and copying.

public void push(E x) {
  if (top == data.length - 1)
    resize(2 * data.length);
  data[++top] = x;
}
private void resize(int newCap) {
  E[] bigger = (E[]) new Object[newCap];
  for (int i = 0; i <= top; i++)
    bigger[i] = data[i];
  data = bigger;
}

Instead of throwing, the new push calls resize(2 * data.length), which allocates the larger array, copies the items at indices 0 to top to the same indices, and points data at the new array. The old array is now unreferenced, and the garbage collector reclaims it. Then data[++top] = x runs as usual.

A resizing push copies n items and so takes O(n). But resizes are rare: since the capacity doubles each time, a resize is followed by as many cheap pushes as there were items before it. The cost of the expensive operations is spread over the cheap ones in between.

This generalizes. The copy counts 4, 8, 16 each double the previous one, and such a sum is less than twice its last term. The last resize copies fewer than n items, so all copies together stay below 2n.

The theorem does not make every push fast: the 17th push of Example 7.2 made 16 copies. In a game or real-time system where every operation must be quick, only the worst case counts.

Growing by a fixed amount instead of a factor is far worse. Let the capacity start at 10 and grow by 10 each time it fills (10 → 20 → 30 → …). Resizes happen at 10, 20, 30, … items, and the copies total 10 + 20 + 30 + … . For n = 100 that is 10 + 20 + … + 90 = 450, and in general about n²/20. The total cost is O(n²), or O(n) per push on average. For 1000 pushes, doubling makes 1023 copies; growing by 10 makes 49,500.

7.2.7The linked-list stack

The second implementation keeps items in a chain of linked nodes. Each node has two fields: the item’s value and a reference to the next node.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }   // next = null
}

In Node, data is the value and next refers to the node below. The constructor sets only data; unassigned reference fields default to null in Java, so a new node’s next is null.

Properties of this implementation:

• Flexible size. Each push allocates a node, so the size adapts at run time; there is no overflow until memory runs out.
• Extra memory. Each node stores a next reference besides its value. For small items such as an int, the reference can take as much space as the item or more.
• No random access, but a fast top. Reaching the kth item takes k steps from the head. A stack, though, needs only its top, which is the head, and the top reference points straight at it.
• Insertion and removal in O(1). Both happen at the head and change only a few references.

Why the head and not the tail? In a singly linked list each node knows only its successor. Deleting the last node means setting the second-to-last node’s next to null, and reaching that node requires walking from the head: O(n). Deleting the head merely advances the head reference: O(1). With the top at the head, both operations are constant-time.

7.2.8Code trace: push on a linked list

The linked stack’s fields and push method:

Node top;          // top of the stack
int size;

public void push(int data) {
  Node temp = new Node(data);
  temp.next = top;
  top = temp;
  size++;
}

top refers to the top node and size counts the items; an empty stack has top = null and size = 0. push takes four steps: create the node, held by the local variable temp; link its next to the old top; point top at it; increment size. We trace push(10) and then push(15) on an empty stack.

On the first push(10), top is null, so temp.next = top leaves next null and the node stands alone. When the method returns, the local temp vanishes but the node survives, now reachable through top.

On the second push, node 15 is not yet in the list when created; top still points to 10. temp.next = top links 15 to the old top, and only then does top = temp move the top. Nothing is shifted and just two references change, so push is O(1).

7.2.9Code trace: pop on a linked list

The pop method, and a loop calling it three times:

public int pop() {
  if (top == null)
    throw new RuntimeException("empty");
  int result = top.data;
  top = top.next;
  size--;
  return result;
}
// in main (stack: 15 → 10):
for (int k = 0; k < 3; k++)
  System.out.println(pop());

If top == null, pop throws RuntimeException("empty"). Otherwise it saves the top value in result, advances top to the node below, decrements size, and returns the value. The value must be saved before the node is unlinked: once top moves, the old top node is unreachable.

On the first call, top = top.next moves the top down to node 10. Nothing refers to the old node 15 any more, and the garbage collector will reclaim it. No explicit null is needed, unlike in the array stack, because top was the node’s only reference and it has moved on. The second call sets top to null, emptying the stack. The third finds the stack empty and throws, and since nothing catches the exception, the program stops.

Without the emptiness check, top.data would dereference null on the third call and throw NullPointerException. The program stops either way, but a descriptive exception names the cause, not just a symptom.

7.2.10Array or linked list?

Both implementations perform the basic operations in O(1), so the choice rests on secondary criteria such as memory use and capacity behavior.

The table shows a trade-off. The array uses less memory per item, but its unused capacity may be wasted; the linked list keeps no spare capacity but carries a reference per item. A dynamic array occasionally copies O(n) items in one push, while a linked list allocates an object on every push, a constant but not negligible cost. Thanks to the cache, the array-based stack is usually faster in practice.

For new Java code, the recommended stack is the Deque interface with the ArrayDeque class:

Deque<Integer> s = new ArrayDeque<>();

It provides push, pop, and peek. A Deque (double-ended queue) allows insertion and removal at both ends; as a stack it uses only the front. The old java.util.Stack extends Vector, whose methods are all synchronized: each call takes a lock against simultaneous access by several threads, a needless slowdown in single-threaded programs. Inheritance from Vector also exposes operations foreign to a stack, such as inserting at an arbitrary index. The rest of these notes therefore use ArrayDeque.

7.3Stack applications

The problems in this section look unrelated: browser history, function calls, parentheses, number sequences. Yet each asks one question, “Which item, seen most recently, is still unresolved?”, and a stack answers it in constant time.

7.3.1Where stacks are used

Stacks appear throughout computer science:

• Expressions. Converting between infix, prefix, and postfix, evaluating postfix, and checking parentheses (7.5 and 7.3.5).
• Undo / redo in text editors.
• Browser history. “Back” and “forward” are managed with two stacks.
• The call stack. Function calls, local variables, and return addresses.
• Backtracking. In maze solving, n-queens, or the Knight’s Tour, returning to the latest decision point after a dead end.
• Algorithms. Towers of Hanoi, tree traversal, stock span, histogram problems.
• Graph algorithms. Depth-first search (DFS), topological sorting, strongly connected components.
• String reversal. Characters go in in order and come out reversed.
• Next greater element. For each item of an array, the first larger value to its right.

In each, jobs start nested and finish in reverse order: the latest decision is undone first, the last bracket opened closes first, the last method called returns first. Such nesting is exactly what LIFO models.

7.3.2Back and forward in a browser: two stacks

A browser runs “back” and “forward” on two stacks. The back stack holds pages visited before the current one, the forward stack pages left by going back; the current page sits in its own variable. The operations:

• visit(s): push the current page onto the back stack, clear the forward stack, and make s current.
• back(): push the current page onto the forward stack; the page popped from the back stack becomes current.
• forward(): push the current page onto the back stack; the page popped from the forward stack becomes current.

Every operation is O(1) except clearing the forward stack, and even that is O(1) if we swap in a fresh empty stack. Undo/redo works the same way: the undo stack holds changes, the redo stack undone ones, and a new change clears the redo stack.

7.3.3The call stack

Every method call gets a record in memory holding its parameters, its local variables, and where execution resumes afterward (the return address). This stack frame lives on the call stack: a call pushes it, a return pops it, and control passes to the caller, now on top.

A method that calls itself, which is called recursion, shows the call stack most clearly. This one computes n! = n · (n − 1) · … · 1.

int fact(int n) {
  if (n <= 1)
    return 1;
  return n * fact(n - 1);
}
// in main:
System.out.println(fact(3));

The case n <= 1, answered directly without a recursive call, is the base case. Every other case computes n * fact(n - 1), and the multiplication must wait until fact(n - 1) finishes.

The stack grows in steps 2–4 and shrinks in steps 5–7; this shrinking after the base case is called unwinding. Each suspended frame resumes when the frame above it returns: fact(2) finishes its multiplication with the 1 from fact(1).

The call stack is at most n frames deep, so fact(n) uses O(n) memory. Its size is limited: very deep recursion, or recursion that never reaches its base case, fills it, and Java throws StackOverflowError, an overflow of the call stack.

7.3.4Reversing a string

Items pushed in order come out reversed, which is all we need to reverse a string.

String reverse(String str) {
    Deque<Character> stack = new ArrayDeque<>();
    char[] chars = str.toCharArray();
    for (char c : chars)
        stack.push(c);
    for (int i = 0; i < str.length(); i++)
        chars[i] = stack.pop();
    return new String(chars);
}
// in main:
System.out.println(reverse("ABCD"));

The stack is a Deque<Character> because Java generics take wrapper classes (Character), not primitives (char); push(c) converts automatically. toCharArray() copies the characters into a new array, and since a String is immutable, the result is built by overwriting that array.

The first loop pushes the characters; the second refills the array from i = 0 with popped ones. For "ABCD" the stack becomes A, B, C, D bottom to top; the first pop gives D, so chars[0] = 'D', then C, B, A follow. The result is "DCBA".

Each character is pushed and popped once: O(n) time, and the stack and array need O(n) extra memory. The same idea tests for a palindrome, a word that reads the same backward (“kayak”): compare the reversed string with the original.

7.3.5Balanced parentheses: the problem and the algorithm

One of a compiler’s first jobs is checking that brackets match. Simplified, let the string S consist only of ( ) { } [ ].

The second condition is the LIFO rule itself, so the algorithm keeps the unmatched opening brackets on a stack and scans S once:

1. An opening bracket is pushed to await its closing partner.
2. For a closing bracket: if the stack is empty, S is invalid (nothing to close). Otherwise pop; if the popped bracket is not of the same type, S is invalid.
3. At the end of S, it is valid if the stack is empty and invalid otherwise (some bracket was never closed).

The kinds of error it catches:

([)] shows why counting is not enough: one opener and one closer of each type, so the counts balance, but the order is wrong. A counter misses this; a stack does not.

7.3.6Code: isBalanced()

boolean isBalanced(String s) {
  Deque<Character> stack = new ArrayDeque<>();
  for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
      stack.push(c);
    } else {
      if (stack.isEmpty()) return false;
      char open = stack.pop();
      if (!matches(open, c)) return false;
    }
  }
  return stack.isEmpty();
}

A helper method says whether an opener and a closer are of the same type:

boolean matches(char open, char close) {
  return (open == '(' && close == ')')
      || (open == '[' && close == ']')
      || (open == '{' && close == '}');
}

isBalanced pushes each opener. For a closer it returns false if the stack is empty; otherwise it pops the latest opener into open and returns false if matches(open, c) fails. Finally, return stack.isEmpty(); reports whether any bracket was left unclosed.

matches joins the three valid pairs with || (or); && (and) requires both halves of a pair. For matches('[', ')') no pair holds: false.

Each character costs O(1): O(n) time. At worst (all openers) the stack holds n items: O(n) memory.

7.3.7Code trace: a valid string

We trace isBalanced("{{[]}()}[]"). The string has ten characters, at indices 0 to 9.

Whenever a closer arrives, the nearest open opener is on top: the } at index 4 matches the { at index 1, the one at index 7 matches index 0, found by LIFO alone with no searching. The stack is briefly empty after index 7, so that prefix is valid on its own. At the end it is empty, and the method returns true.

7.3.8Invalid strings

The algorithm returns false in three places, each for a different error.

Returning early is a bonus: once an error is found, the rest need not be read. The worst case stays O(n), but invalid input often finishes much sooner.

The same algorithm checks that HTML tags such as <b><i>…</i></b> nest properly: push each opening tag, pop on each closing tag, and compare names.

7.3.9Next greater element

Given an array of numbers, find for each item the first item to its right that is larger, or −1 if there is none. This is the next greater element problem.

By hand: right of 4, the first larger item is 7. Right of 7, 3 and 4 are smaller, so the answer is 8. The 4 next to 3 is larger. Right of 8 there is only 1: −1. The last item has nothing to its right: −1.

Brute force scans right from each item to the first larger one. On a decreasing array every scan runs to the end: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons, O(n²) time.

A stack does it in O(n). Scan right to left, keeping only “candidates” on the stack: values that could still answer for items further left. When x arrives, pop every value on top that is at most x. These lie right of x and are no larger; any item left of x meets x first, and if x is not big enough, neither are they, so they can never answer again. The first value not popped, if any, is the answer for x, which is then pushed as a candidate.

int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = arr.length-1; i >= 0; i--) {
        while (!stack.isEmpty() &&
               stack.peek() <= arr[i])
            stack.pop();
        result[i] = stack.isEmpty()
                 ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return result;
}

The stack therefore stays decreasing bottom to top, since each item is pushed only after everything at most its size is gone. A stack whose contents stay sorted is a monotonic stack.

This is amortized analysis again: one outer turn may run the inner loop many times, but the total is bounded. Nested loops do not automatically mean quadratic time; count the inner loop’s total runs.

7.3.10Code trace: nextGreater()

Initially result is all zeros (Java zero-fills a new int array) and the stack is empty. At i = 5 the answer is −1, and 1 becomes a candidate. At i = 4 the 1 on top is popped: it cannot answer for anything left of 8, since 8 is larger and nearer. The stack empties; 8’s answer is −1.

Row i = 1 shows the method best. With 8, 4, 3 on the stack, the incoming 7 pops 3 and 4 and stops at 8, since 8 <= 7 is false; the answer is 8, and 3 and 4 are useless to anything left of 7. At i = 0 the 7 on top beats 4 at once. The method returns [7, 8, 4, 8, −1, −1] after six pushes and three pops, as Theorem 7.2 allows.

7.3.11A stack that returns its minimum in O(1)

Now add getMin(), returning the smallest value on the stack. Scanning takes O(n); we want O(1), like the other operations.

The solution is a second stack. s holds all items; the top of min is always the smallest value in s. A value no larger than the current minimum also goes onto min, and a value leaving s that equals the top of min leaves min too, restoring the previous minimum.

Deque<Integer> s = new ArrayDeque<>();
Deque<Integer> min = new ArrayDeque<>();
void push(int x) {
  s.push(x);
  if (min.isEmpty() || x <= min.peek())
    min.push(x);
}
int pop() {
  int x = s.pop();
  if (x == min.peek()) min.pop();
  return x;
}
int getMin() { return min.peek(); }

Each operation does at most two pushes, two pops, or a peek, all O(1); getMin() is just min.peek(). The price is memory: with pushes in decreasing order, min also holds n items, O(n) extra.

The x == min.peek() test in pop is subtle too. x is an int and min.peek() an Integer, so Java unboxes and compares values, correctly. Were both sides Integer, == would compare object identity and could fail for values above 127; then use equals.

7.4Towers of Hanoi and stock span

Two more uses of a stack. In the Towers of Hanoi it makes recursion’s hidden call stack explicit; in stock span it keeps “candidates,” as in next greater element, turning a quadratic solution into a linear one.

7.4.1Towers of Hanoi without recursion

The puzzle has three pegs (A, B, C) and n disks of different sizes, stacked on A largest at the bottom, to be moved in the same order to C. Each move takes one top disk, and a larger disk may never go on a smaller one. Each peg is a stack: only its top disk is accessible.

The classic solution is recursive. To move n disks from A to C using B:

1. move the top n − 1 disks from A to B (using C);
2. move the largest disk from A to C;
3. move the n − 1 disks from B to C (using A).

A single disk (the base case) moves directly. Recursively, the call stack holds the pending subtasks: while step 1 runs, steps 2 and 3 wait. An explicit stack can store each pending job as a task instead.

// Task: move n disks from peg 'from' to peg 'to' via 'via'
record Task(int n, char from, char via, char to) {}

void hanoi(int n) {
  Deque<Task> stack = new ArrayDeque<>();
  stack.push(new Task(n, 'A', 'B', 'C'));
  while (!stack.isEmpty()) {
    Task t = stack.pop();
    if (t.n() == 1)
      System.out.println(t.from() + " → " + t.to());
    else {                         // in reverse order
      stack.push(new Task(t.n()-1, t.via(), t.from(), t.to()));
      stack.push(new Task(1, t.from(), t.via(), t.to()));
      stack.push(new Task(t.n()-1, t.from(), t.to(), t.via()));
    }
  }
}

A record (Java 16) is a compact class: Task is an immutable object with four fields, read through methods such as t.n() and t.from(): the disk count n and the source, auxiliary, and destination pegs from, via, to. (3, A, B, C) means “move 3 disks from A to C using B.”

The method pushes the initial task and pops tasks until the stack is empty. A one-disk task is done at once by printing the move. Any other is split into the three subtasks above, pushed in reverse order: step 3 (n−1, via, from, to), step 2 (1, from, via, to), then step 1 (n−1, from, to, via), which thus lands on top and comes off next.

The reverse order is LIFO at work. In natural order, step 3 would run first, moving disks from B to C that have not yet left A.

7.4.2Code trace: hanoi(3)

Table 7.15 shows every iteration of hanoi(3). The stack column lists tasks (n,from,via,to) top to bottom, so the first comes off next.

In iteration 1, with t.n()-1 = 2, t.via() = B, t.from() = A, t.to() = C, the pushes are (2,B,A,C), (1,A,B,C), (2,A,C,B), leaving “move 2 disks from A to B” on top. Iteration 2 splits it into three one-disk tasks, and iterations 3–5 move the two smallest disks to B (A → C, A → B, C → B). Iteration 6 moves the largest disk from A to C, step 2 of the first split. Iteration 7 splits the remaining “move 2 disks from B to C,” and 8–10 finish it.

There are 7 = 2³ − 1 moves; in general n disks need 2ⁿ − 1, since T(n) = 2T(n − 1) + 1 and T(1) = 1. Slightly more tasks are popped: one per move plus the split ones, so for n = 3, 7 + 3 = 10 iterations. The time is O(2ⁿ), a lower bound for the problem itself, since every move must be printed.

Memory is far better: the trace never had more than 5 tasks. Each split replaces one task with three, growing the stack by two, and at most n − 1 splits can stack up (each lowers the disk count). So the stack holds at most 1 + 2(n − 1) = 2n − 1 tasks, O(n): 5 for n = 3, 7 for n = 4.

An explicit stack puts pending work under the program’s control. The runtime limits the call stack, so deep recursion throws StackOverflowError, while an explicit stack grows on the heap. The same transformation works for other recursive algorithms, such as depth-first search.

7.4.3The stock span problem

Given a stock’s daily closing prices, financial analysts often ask how many days today’s price has gone unexceeded: the stock span problem.

Note three details: every span is at least 1, since today counts; equal prices count; and days must be consecutive, so the count ends at the first higher price even if lower ones lie beyond.

Brute force walks back from each day to a higher price. With steadily rising prices every walk reaches the start: 1 + 2 + … + n steps, O(n²). A stack removes the repeated walking.

7.4.4Code: span()

int[] span(int[] prices) {
    int[] spans = new int[prices.length];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0); spans[0] = 1;
    for (int i = 1; i < prices.length; i++) {
        while (!stack.isEmpty() &&
            prices[i] >= prices[stack.peek()])
            stack.pop();
        spans[i] = stack.isEmpty() ? i + 1
                              : i - stack.peek();
        stack.push(i);
    }
    return spans;
}

The idea is next greater element’s, but scanning left to right with indices on the stack: those of days not yet exceeded, with prices decreasing bottom to top. When day i arrives, days priced at or below today are popped. They can never limit a future day: today has exceeded them and is a nearer, higher (or equal) barrier.

The top is then the latest earlier day with a higher price, and the span is the distance to it, i - stack.peek(). If the stack is empty, today beat every earlier price and the span is i + 1 (days 0 to i). Finally today is pushed as a possible future barrier.

The first day, with span 1, is handled before the loop by stack.push(0); spans[0] = 1;, so the loop starts at i = 1. Since the stack holds indices, the condition prices[i] >= prices[stack.peek()] reaches prices through them.

The cost argument is that of next greater element: each index is pushed once and popped at most once, so time and memory are O(n).

7.4.5Code trace: span()

At i = 3, 70 beats day 2 (60), which is popped: day 3 (70) is nearer and higher for any later day. Day 1 (80) is on top, so the span is 3 − 1 = 2. At i = 5, 75 pops days 4 (60) and 3 (70) and stops at day 1 (80): span 5 − 1 = 4. At i = 6, 85 pops days 5 (75) and 1 (80) and stops at day 0 (100): span 6. The result [1, 1, 1, 2, 1, 4, 6] matches Example 7.5, after 7 pushes and 5 pops.

7.5Expression notations

An expression like 3 + 4 * 2 is easy for people but hard for a computer in two ways: the multiplication is done before the addition written to its left, and parentheses, possibly nested, change the order. This section writes expressions in two forms that make the order explicit, and converts between them with a stack.

7.5.1Infix, prefix, and postfix

An expression has operands (A, B, 5) and operators (+, −, *, /). The three notations differ in where the operator goes.

Everyday notation is infix, as in B + C. In prefix the operator comes first, + B C; this is Polish notation, after the logician Jan Łukasiewicz, who proposed it in the 1920s. In postfix it comes last, B C +: reverse Polish notation, or RPN.

To read postfix, scan A B C + * D / from the left; at each operator, the two values just before it are its operands and are replaced by the result. B C + → (B + C); then A (B + C) * → A * (B + C); then … D / → (A * (B + C)) / D.

Prefix and postfix need neither parentheses nor precedence rules: the order of operations follows from the sequence of symbols. Postfix is evaluated left to right, prefix right to left, in one pass with a stack, which is why compilers and interpreters usually convert to postfix. Java bytecode is stack-based: a + b becomes “push a, push b, add.” Some calculators (older HP models) work in RPN, as do symbolic algebra programs and expression-tree algorithms.

7.5.2Precedence, associativity, and converting by hand

Infix needs two rules: precedence says which of two different operators goes first, and associativity in which direction equal-precedence operators apply.

Left associativity makes A − B + C mean (A − B) + C: 10 − 4 + 3 is 6 + 3 = 9, whereas grouping from the right gives 10 − 7 = 3. Its postfix is A B − C +. Exponentiation is right-associative: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2) = 29 = 512, not (2 ^ 3) ^ 2 = 64.

To convert by hand, use full parenthesization:

1. Following precedence and associativity, put every operation in its own parentheses.
2. For postfix, move each operator to the right end of its parentheses and delete the parentheses.
3. For prefix, move each operator to the left end of its parentheses and delete the parentheses.

A quick check: operands keep the same order in all three notations; only operators move. A conversion that scrambles the operands is certainly wrong. The converse fails: operands can be in order with operators misplaced (like * A / + B C D in 7.5.1).

7.5.3Infix to postfix: the algorithm

A program would have to parse the whole expression to parenthesize it. Edsger Dijkstra’s 1961 shunting-yard algorithm, named after a railway switching yard, instead makes one left-to-right pass: operators and opening parentheses wait on a stack, operands go straight to the output.

The reasoning: a newly read operator still lacks its right operand, so it waits on the stack. When op arrives, waiting operators of precedence at least op’s have complete operands and must be applied first, so they are output; lower ones apply after op and keep waiting.

Popping on equality (≥) reflects left associativity: in A − B + C, when + arrives, the equal − must go first and is output, giving A B − C +. For right-associative ^, only strictly greater precedence (>) pops, so in A ^ B ^ C the second ^ goes above the first and applies first.

A parenthesis walls off precedence: operators pushed after ( never look beneath it, and ) pops only down to it. Parentheses are never output; postfix needs none.

Each symbol is read once and each operator pushed and popped once: O(n) time for an expression of length n, and O(n) stack memory at worst.

7.5.4Code: infixToPostfix()

String infixToPostfix(String expr) {
  StringBuilder out = new StringBuilder();
  Deque<Character> stack = new ArrayDeque<>();
  for (char c : expr.toCharArray()) {
    if (Character.isLetterOrDigit(c)) out.append(c);
    else if (c == '(') stack.push(c);
    else if (c == ')') {
      while (stack.peek() != '(')
        out.append(stack.pop());
      stack.pop();                  // discard '('
    } else {                        // operator
      while (!stack.isEmpty() &&
          prec(stack.peek()) >= prec(c))
        out.append(stack.pop());
      stack.push(c);
    }
  }
  while (!stack.isEmpty()) out.append(stack.pop());
  return out.toString();
}

The helper that gives the precedences:

int prec(char op) {
  switch (op) {
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    default: return 0;   // '('
  }
}

The code applies the five rules of Table 7.19 in order. A letter or digit (Character.isLetterOrDigit(c)) is an operand and is appended to out, a StringBuilder, Java’s efficient way to build a string piece by piece. A ( is pushed. On ), while (stack.peek() != '(') outputs the operators down to the (, and one more stack.pop() discards it. Anything else is an operator: the while loop pops while the top’s precedence is not lower than the incoming one’s, then pushes the newcomer. At the end the remaining operators are appended.

The condition “the top is not (” is handled by prec: its default branch gives ( precedence 0, below every real operator, so prec('(') >= prec(c) is never true. Only ) pops a (.

The code assumes single-character operands, only + − * / (no ^), no spaces, and a valid expression. Given a ) with no matching (, stack.peek() returns null on the empty stack, and null != '(' throws NullPointerException while unboxing the Character.

7.5.5Code trace: A*(B+C)/D

The decisive moment is reading /: the ≥ rule outputs the equal-precedence *, which is on the left in infix and goes first. Had it stayed, the result would be A B C + D / *, meaning A * ((B + C) / D). The result matches the hand conversion of Example 7.6.

7.5.6Code trace: A+B*C-D/E

With no parentheses, precedence does all the work.

At *, the lower-precedence + keeps waiting and * goes on top: the stack’s version of “multiplication first.” At -, two operators leave: the higher *, then the equal +. At the end the stack empties from the top, / then −. The result A B C * + D E / − means (A + B·C) − D/E.

7.5.7Evaluating a postfix expression

The payoff of postfix is trivial evaluation. Read left to right:

1. Push each number.
2. On an operator, pop two items, the right operand first, then the left; apply the operator and push the result.
3. At the end, one item remains on the stack: the result.

No parentheses or precedence are involved; each symbol is handled once: O(n).

A helper does the arithmetic:

int apply(int left, char op, int right) {
  switch (op) {
    case '+': return left + right;
    case '-': return left - right;
    case '*': return left * right;
    default:  return left / right;
  }
}

The evaluation method:

int evaluatePostfix(String expr) {
  Deque<Integer> stack = new ArrayDeque<>();
  for (char c : expr.toCharArray()) {
    if (Character.isDigit(c)) {
      stack.push(c - '0');
    } else {
      int right = stack.pop();
      int left = stack.pop();
      stack.push(apply(left, c, right));
    }
  }
  return stack.pop();
}

c - '0' turns a digit character into its value: characters are numeric codes, and '0' through '9' are consecutive, so '7' - '0' is 7. On an operator, the first pop goes into right, the second into left, and apply(left, c, right) is pushed. A final pop returns the result. The code assumes single-digit numbers, no spaces, and a valid expression; / is integer division, so 7 / 2 is 3.

Why right first? The left operand was read, and pushed, earlier, so it sits lower. For addition and multiplication this is irrelevant, but not for subtraction and division: in 5 2 −, the first pop gives 2 (right), the second 5 (left), and the result is 5 − 2 = 3, not 2 − 5 = −3.

7.5.8Code trace: evaluatePostfix()

Substituting A = 4, B = 1, C = 2, D = 3 into A B C + * D / from Example 7.6 gives the postfix string "412+*3/", whose infix equivalent is 4 · (1 + 2) / 3 = 4.

The stack holds intermediate results not yet used by an operator; at +, 1 and 2 are replaced by 3. The stack sizes (1, 2, 3, 2, 1, 2, 1) also reveal validity: each number adds one, each binary operator removes one, and in a valid expression the stack holds at least 2 items at every operator and exactly 1 at the end.

7.5.9Infix to prefix

Infix to prefix needs no new algorithm, just the postfix one, slightly modified, between two reversals:

1. Reverse the infix expression.
2. Swap the parentheses: ( ↔ ).
3. Apply the postfix algorithm, but do not pop on equal precedence: pop only operators of strictly greater precedence (>).
4. Reverse the output.

Prefix is the mirror image of postfix. Reversal flips each operator’s position relative to its operands, so taking the postfix of the reversed expression and reversing it puts each operator in front. Reversal also flips the parentheses, which step 2 corrects.

The “no pop on equal” rule preserves associativity, which reversal turns from left to right. When * arrives in the reversed expression, the equal / stays and * goes above it, so * applies first, and after the final reversal A * (B + C) still precedes / D. Popping on equality would give D C B + / A * and the prefix * A / + B C D, the very mistake of 7.5.1.

For the second example, A + B * C − D / E, the same method yields − + A * B C / D E, the hand result of Example 7.6.

7.5.10Code trace: infixToPrefix()

String rev(String s) {
  return new StringBuilder(s).reverse().toString();
}
String infixToPrefix(String expr) {
  String t = rev(expr);            // 1. reverse
  t = swapParens(t);               // 2. ( ↔ )
  String p = postfixForPrefix(t);  // 3. no pop on equal
  return rev(p);                   // 4. reverse
}
// in main:
System.out.println(infixToPrefix("A*(B+C)/D"));

Four steps, four lines. rev uses StringBuilder’s built-in reverse(). swapParens, whose body the slides omit, swaps ( and ):

String swapParens(String s) {
  StringBuilder sb = new StringBuilder();
  for (char c : s.toCharArray()) {
    if (c == '(') sb.append(')');
    else if (c == ')') sb.append('(');
    else sb.append(c);
  }
  return sb.toString();
}

postfixForPrefix copies infixToPostfix except for the operator-branch comparison:

for (char c : expr.toCharArray()) {
  if (Character.isLetterOrDigit(c)) out.append(c);
  else if (c == '(') stack.push(c);
  else if (c == ')') {
    while (stack.peek() != '(')
      out.append(stack.pop());
    stack.pop();                  // discard '('
  } else {                        // operator
    while (!stack.isEmpty() &&
        prec(stack.peek()) > prec(c))
      out.append(stack.pop());
    stack.push(c);
  }
}
while (!stack.isEmpty()) out.append(stack.pop());

With > instead of >=, an equal-precedence operator stays. The trace for the reversed, swapped input "D/(C+B)*A":

Reversing p = "DCB+A*/" gives "/*A+BCD", which main prints; the operands are still in order A, B, C, D.

Each of the four steps (two reversals, one parenthesis swap, one conversion) is O(n), so the whole is O(n).

7.5.11Evaluating a prefix expression

Prefix evaluation follows the postfix rules with two changes: read right to left, and the first pop is the left operand, since reading from the right pushes the right operand first and the left one ends up on top.

Postfix and prefix evaluation are one stack idea run in two directions: the stack holds operands awaiting an operator, and only the reading direction, hence the pop order, differs.

7.6Common mistakes and a common pattern

Most stack bugs fall into a few types. The table gathers the chapter’s mistakes into a checklist for reviewing stack code.

Iteration order comes from library internals. java.util.Stack, a Vector, keeps items in insertion order, so toString() and for-each go bottom to top. ArrayDeque’s push inserts at the front, where iteration starts, so it goes top to bottom. After pushing 1, 2, 3, Stack prints [1, 2, 3] and ArrayDeque [3, 2, 1]: same contents, opposite output.

One pattern runs through the chapter. A stack is the right tool when the question is “Which item, seen most recently, is still unresolved?”: the latest bracket opened but not closed, the latest method called but not returned, the latest intermediate result not yet used, the nearest candidate not yet exceeded (next greater element, stock span), the latest subtask not yet done (Hanoi). When a problem raises this question, its solution very likely uses a stack.

7.7Summary

• A stack is a LIFO (last-in, first-out) ADT with insertion and removal only at the top. push, pop, top/peek, isEmpty, and size are all O(1); searching is O(n); n items take O(n) memory.
• Popping an empty stack is underflow; pushing onto a full bounded stack is overflow. Libraries treat empty stacks differently, so check isEmpty() before pop and peek.
• In an array-based stack, top is the last item’s index (−1 when empty) and size = top + 1; vacated object cells are set to null. A dynamic array doubles when full: a resizing push is O(n), but n pushes cost under 3n, so push is amortized O(1). Growing by a fixed amount costs O(n²) in total.
• In a linked-list stack the top is the head, where push and pop work in O(1). It overflows only when memory runs out, and each node carries an extra reference. New Java code should use Deque<E> s = new ArrayDeque<>().
• A browser’s back/forward uses two stacks, method calls the call stack. Recursion needs memory proportional to its depth; without a base case it ends in StackOverflowError.
• Balanced parentheses keeps unmatched openers on a stack and catches three kinds of error (wrong order, unclosed, extra closer) in O(n).
• Next greater element and stock span are solved in O(n) with a monotonic stack, decreasing bottom to top, because each item is pushed once and popped at most once. A stack with O(1) getMin() keeps the minima on a second stack (using <=).
• The Towers of Hanoi yield to an explicit task stack that pushes subtasks in reverse order: 2ⁿ − 1 moves, O(n) stack.
• Infix becomes postfix in O(n) with an operator stack, popping while the top’s precedence is ≥ the incoming one’s. For prefix: reverse, swap parentheses, convert without popping on equality, reverse again. Operands keep their order in all three notations.
• Postfix evaluation reads left to right; at an operator the first pop is the right operand, the second the left. Prefix is read right to left, and the first pop is the left operand.

7.8Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• stack
• top
• push
• pop
• LIFO (last-in, first-out)
• abstract data type (ADT)
• interface
• generic
• overflow
• underflow
• capacity
• dynamic array
• amortized analysis
• linked list
• singly linked list
• node
• reference
• undo
• call stack
• stack frame
• recursion
• base case
• backtracking
• balanced parentheses
• next greater element
• stock span
• infix
• prefix
• postfix
• depth-first search (DFS)
• time complexity
• space complexity

7.9Test Yourself

1. An empty stack receives push(7), push(2), pop(), push(9), top(), push(4), pop(), pop(). What do the calls return, and what is left?

   Answer

   The first pop() returns 2, leaving 7. After push(9), top() returns 9 without removing it. After push(4) the stack is 7 9 4; the pops return 4, then 9. The values are 2, 9, 4, 9, and only 7 remains.

2. What do isBalanced("([]{})") and isBalanced("([]{)}") return? For the invalid one, at which character is the error detected?

   Answer

   The first returns true: (, [ pushed; ] pops [; { pushed; } pops {; ) pops (; the stack ends empty. The second returns false: when the ) at index 4 arrives, the stack is ( { and the pop yields {; matches('{', ')') is false. The final } is never read.

3. What are the postfix and prefix forms of (A + B) * C − D / (E + F)?

   Answer

   Fully parenthesized: (((A + B) * C) − (D / (E + F))). Postfix: A B + C * D E F + / −. Prefix: − * + A B C / D + E F. The operands stay in order A to F in both. In infixToPostfix, - pops the *, while at / the lower-precedence - stays.

4. What is the value of the postfix expression 7 2 − 3 * 8 4 / +? What is on the stack after each operator?

   Answer

   −: right 2, left 7 → 5; stack 5. *: right 3, left 5 → 15; stack 15. /: right 4, left 8 → 2; stack 15 2. +: right 2, left 15 → 17. The value is 17; in infix, (7 − 2) · 3 + 8 / 4.

5. What are the spans for prices [50, 40, 45, 60, 55, 70]? How many pops does span make in total?

   Answer

   Spans: [1, 1, 2, 4, 1, 6]. At i = 2, 45 pops day 1 (40) and stops at day 0 (50): 2 − 0 = 2. At i = 3, 60 pops days 2 and 0, emptying the stack: 3 + 1 = 4. At i = 5, 70 pops days 4 and 3, emptying it: 6. That is 5 pops (indices 1, 2, 0, 4, 3), fewer than the 6 pushes.

6. What is the next greater element array for {3, 8, 2, 5, 1, 9}? Which values are popped at step i = 1?

   Answer

   The result is [8, 9, 5, 9, 9, −1]. Right to left: 9 → −1; 1 → 9; 5 pops 1 → 9; 2 → 5; at i = 1 8 arrives with the stack 9 5 2 bottom to top, pops 2 and then 5, and the 9 left on top is the answer. Finally 3 → 8.

7. An empty stack of capacity 2 that doubles when full receives 12 pushes. How many resizes and copies are made? Is the total cost below 3n?

   Answer

   Resizes occur on the 3rd push (2 → 4, 2 copies), the 5th (4 → 8, 4 copies), and the 9th (8 → 16, 8 copies): 3 resizes, 14 copies. With 12 writes the total is 26, below 3 · 12 = 36. The final capacity is 16.

8. Which moves does the stack version of hanoi(2) print? Which tasks are on the stack (top to bottom) after the first iteration?

   Answer

   In the first iteration (2,A,B,C) is split, and the stack, top to bottom, becomes (1,A,C,B), (1,A,B,C), (1,B,A,C). The next three iterations carry them out: A → B, A → C, B → C, a total of 2² − 1 = 3 moves.

9. Suppose the min stack’s push condition reads x < min.peek() instead of x <= min.peek(). What happens on push(2), push(2), pop(), getMin() from an empty stack?

   Answer

   The first 2 goes onto min; the second does not, as 2 < 2 is false. pop() removes a 2, and since 2 == min.peek(), the only 2 in min goes too. s still holds a 2 but min is empty, so min.peek() in getMin() returns null, and unboxing it to int throws NullPointerException.

10. What is the value of the prefix expression / * 4 + 1 2 3?

    Answer

    Right to left: 3, 2, 1 are pushed (stack 3 2 1). +: left 1 (first pop), right 2 → 3; stack 3 3. Push 4; stack 3 3 4. *: left 4, right 3 → 12; stack 3 12. /: left 12, right 3 → 4. The value is 4; in infix, 4 · (1 + 2) / 3.

7.10Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Section 6.1: the stack ADT, array and linked-list implementations, and bracket matching and HTML tag checking, in Java code close to these notes.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.3: stacks implemented with a dynamic array and a linked list, and Dijkstra’s two-stack expression evaluation algorithm in a short, clear example.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed., 2009), Sections 10.1 and 17.4: the array implementation of a stack and the amortized analysis of dynamic tables, in more formal language.

7.11References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
2. E. W. Dijkstra, “Algol 60 translation: An Algol 60 translator for the X1 and Making a translator for Algol 60”, Report MR 35/61, Mathematisch Centrum, Amsterdam, 1961.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
4. R. Lafore, Data Structures and Algorithms in Java, 2nd ed., Sams, 2002.
5. Oracle, Java SE 17 API Specification: documentation for java.util.Deque and java.util.ArrayDeque.
6. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 7 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.