Stack Interface

• OpenDSA version:

  public interface Stack<E> { // Stack class ADT
    // Reinitialize the stack.
    public void clear();
  
    // Push "it" onto the top of the stack
    public boolean push(E it);
  
    // Remove and return the element at the top of the stack
    public E pop();
  
    // Return a copy of the top element (Often called peek)
    public E topValue();
  
    // Return the number of elements in the stack
    public int length();
  
    // Return true if the stack is empty 
    public boolean isEmpty();
  
  }

Question:

• Why bother with defining a Stack interface?
  • The operations are a subset of List
  • We could always just use an AList or LList
• 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

Warm-up Socrative Question

• What will be printed when this code executes:

  Stack<String> stack = new LStack<>();
  
  stack.push("A");
  stack.push("B");
  stack.push("C");
  stack.pop();
  stack.push("D");
  
  while (!stack.isEmpty()) {
    System.out.print(stack.pop());
  }

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

Stack Applications

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

AStack Implementation

    class AStack<E> implements Stack<E> {
      private E stackArray[];         // Array holding stack
      private static final int defaultSize = 10;
      private int maxSize;            // Maximum size of stack
      private int top;                // First free position at top
    
      // Constructors
      @SuppressWarnings("unchecked") // Generic array allocation
      AStack(int size) {
        maxSize = size;
        top = 0; 
        stackArray = (E[])new Object[size]; // Create stackArray
      }
      AStack() { this(defaultSize); }
    
      public void clear() { top = 0; }    // Reinitialize stack
    
    // Push "it" onto stack
      public boolean push(E it) {
        if (top >= maxSize) return false;
        stackArray[top++] = it;
        return true;
      }
    
    // Remove and return top element
      public E pop() {               
        if (top == 0) return null;
        return stackArray[--top];
      }
    
      public E topValue() {          // Return top element
        if (top == 0) return null;
        return stackArray[top-1];
      }
    
      public int length() { return top; } // Return stack size
    }
    
    // Check if the stack is empty
    public boolean isEmpty() { return top == 0; }

    /*
     * OpenDSA Project Distributed under the MIT License
     * 
     * Copyright (c) 2011-2016 - Ville Karavirta and Cliff Shaffer
     */

• Problems?

Dynamic-Array Based AStack

• Big-\(\Theta\) cost?

  operation	cost
  push()
  pop()
  topValue()
  length()

Dynamic-Array Based AStack

• Big-\(\Theta\) cost?

  operation	cost
  push()	\(\Theta(1)\)*
  pop()	\(\Theta(1)\)
  topValue()	\(\Theta(1)\)
  length()	\(\Theta(1)\)

  * Amortized

Linked Stack Implementation

    // Linked stack implementation
    class LStack<E> implements Stack<E> {
      private Link<E> top;            // Pointer to first element
      private int size;               // Number of elements
    
      // Constructors
      LStack() { top = null; size = 0; }
      LStack(int size) { top = null; size = 0; }
    
      // Reinitialize stack
      public void clear() { top = null; size = 0; }
    
    // Put "it" on stack
      public boolean push(E it) {  
        top = new Link<E>(it, top);
        size++;
        return true;
      }
    
    // Remove "it" from stack
      public E pop() {           
        if (top == null) return null;
        E it = top.element();
        top = top.next();
        size--;
        return it;
      }
    
      public E topValue() {      // Return top value
        if (top == null) return null;
        return top.element();
      }
    
      // Return stack length
      public int length() { return size; }
      
      // Check if the stack is empty
      public boolean isEmpty() { return size == 0; }
    }
    
    /*
     * OpenDSA Project Distributed under the MIT License
     * 
     * Copyright (c) 2011-2016 - Ville Karavirta and Cliff Shaffer
     */

Linked Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()
  pop()
  topValue()
  length()

Linked Stack

• Big-\(\Theta\) cost?

  operation	cost
  push()	\(\Theta(1)\)
  pop()	\(\Theta(1)\)
  topValue()	\(\Theta(1)\)
  length()	\(\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