Stack ADT (from zyBook)

Queue ADT (from zyBook)

Warm-up Socrative Question

• What will be printed when this code executes?

  Stack<String> stack = new ArrayStack<>();
  Queue<String> queue = new ArrayQueue<>();
  
  stack.push("A");
  stack.push("B");
  stack.push("C");
  stack.pop();
  stack.push("D");
  
  while (!stack.isEmpty()) {
    queue.enqueue(stack.pop());
  }
  
  while (!queue.isEmpty()) {
    System.out.print(queue.dequeue());
  }

1. ABCD
2. DCBA
3. CDBA
4. DBA
5. ABD

Deque ADT (from zyBook)

Java Stack Interface

public interface Stack<E> {
  
  void push(E item);
  
  E pop();
  
  E peek();
  
  boolean isEmpty();
  
  int size();
  
}

Question:

• Why bother with defining a Stack interface?
  • The operations are a subset of List
  • We could always just use an ArrayList or LinkedList
• Code is more clear and more safe
• Gives some confidence that the implementation is efficient: tuned to support add and remove at the same end of the collection

Stack Applications

• Undo Operations
• Matching Parentheses
• Postfix expression evaluation
• Implementing recursion

ArrayStack Implementation (Modified from zyBook)

public class ArrayStack<E> implements Stack<E> {

  private static final int INITIAL_CAPACITY = 1;

  private E[] array;
  private int size;

  @SuppressWarnings("unchecked")
  public ArrayStack() {
    array = (E[]) new Object[INITIAL_CAPACITY];
    size = 0;
  }

  public void push(E item) {
    if (size == array.length) {
      resize();
    }
    array[size] = item;
    size++;
  }

  public E pop() {
    E toReturn = array[size - 1];
    size--;
    array[size] = null; // WHY????
    return toReturn;

    // return array[--size]; // could be one line.
  }

  @Override
  public E peek() {
    return array[size - 1];
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  public int size() {
    return size;
  }

  private void resize() {
    int newSize = array.length * 2;
    @SuppressWarnings("unchecked")
    E[] newArray = (E[]) new Object[newSize];
    for (int i = 0; i < size; i++) {
      newArray[i] = array[i];
    }
    array = newArray;
  }

}

Dynamic-Array Based Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()
  pop()
  peek()
  size()

Dynamic-Array Based Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()	\(\Theta(1)\)*
  pop()	\(\Theta(1)\)
  peek()	\(\Theta(1)\)
  size()	\(\Theta(1)\)

  * Amortized

Linked Stack Implementation

public class LinkedStack<E> implements Stack<E>{
  
  private Node top; // No need for a tail reference!
  private int size;
  
  private class Node {
    E item;
    Node next;
    
    public Node(E item, Node next) {
      this.item = item;
      this.next = next;
    }
  }

  @Override
  public void push(E item) {
    top = new Node(item, top);
    size++;
  }

  @Override
  public E pop() {
    E toReturn = top.item;
    top = top.next;
    size--;
    return toReturn;
  }

  @Override
  public E peek() {
    return top.item;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public int size() {
    return size;
  }
  
}

Linked Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()
  pop()
  peek()
  size()

Linked Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()	\(\Theta(1)\)
  pop()	\(\Theta(1)\)
  peek()	\(\Theta(1)\)
  size()	\(\Theta(1)\)

Infix and Postfix (Reverse Polish Notation)

• Infix expression:
  • \(3 + 5 \times 2 - 6\)
  • \(((3 + (5 \times 2)) - 6)\)
• Convert to postfix by moving each operator to the corresponding close-parenthesis:
  • \(3\; 5\; 2 \times + \; 6 \; -\)

Postfix Evaluation Algorithm

for each token:
    if the token is an operand:
        Push the token on the stack
    else: // token is an operator
        Pop two items
        Perform the operation
        Push the result on the stack
return the top of the stack

Exercise

• Convert this infix expression to postfix:
  • \(2 \times 4 \div 8 + 7 \times 3\)
• Evaluate (on paper) using a stack.

Which of the following represents one of the stack configurations that is reached during evaluation? (Top of the stack is on the left.)

A) 2 4 8 \(\div\) \(\times\)

B) 3 7 1

C) 2 4 8

D) 4 8 1