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();
  
  }

Queue Interface

• OpenDSA version:

  public interface Queue<E> { // Queue class ADT
    // Reinitialize queue
    public void clear();
  
    // Put element on rear
    public boolean enqueue(E it);
  
    // Remove and return element from front
    public E dequeue();
  
    // Return front element
    public E frontValue();
  
    // Return queue size
    public int length();
  
    //Tell if the queue is empty or not
    public boolean isEmpty();
  }

Queue Applications

• Queues are ubuiquitous in applications that must connect producers to consumers of data.

Warm-up Socrative Question

• What will be printed when this code executes?

  Stack<String> stack = new AStack<>();
  Queue<String> queue = new AQueue<>();
  
  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

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)\)

Queue Implementation: Circular Arrays

Some Options for Circular Increment:

    
    // Option A
    index++;
    if (index == array.length) {
      index = 0;
    }
    
    // Option B
    if (index == array.length - 1) {
      index = 0;
    } else {
      index++;
    }
    
    // Option C
    index = (index + 1) % array.length;
    

Let’s take a Look at AQueue…

Dynamic-Array Based AQueue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()
  dequeue()
  frontValue()
  length()

Dynamic-Array Based AQueue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()	\(\Theta(1)\)*
  dequeue()	\(\Theta(1)\)
  frontValue()	\(\Theta(1)\)
  length()	\(\Theta(1)\)

  * Amortized

Linked Queue Socrative Question

Which of the following describes the most reasonable organization of a linked queue?

1. enequeue and dequeue are performed at the head. There is no need to maintain a tail reference.

2. enequeue is performed at the tail. dequeue is performed at the head.

3. enequeue is performed at the head. dequeue is performed at the tail.

4. Both a head and tail reference are required, but it doesn’t matter which is used for enequeue and which is used for dequeue.

Linked Queue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()
  dequeue()
  frontValue()
  length()

Linked Queue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()	\(\Theta(1)\)
  dequeue()	\(\Theta(1)\)
  frontValue()	\(\Theta(1)\)
  length()	\(\Theta(1)\)

Bonus Stack Application: 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