Stacks

Stack ADT

• The Stack ADT stores arbitrary objects
• Insertions and deletions follow the last-in first-out scheme
• Think of a spring-loaded plate dispenser
• Main stack operations:
  • push(object): inserts an element
  • object pop(): removes and returns the last inserted element
• Auxiliary stack operations:
  • object top(): returns the last inserted element without removing it
  • integer size(): returns the number of elements stored
  • boolean isEmpty(): indicates whether no elements are stored
• Exceptions
  • Attempting the execution of pop or top on an empty stack throws an EmptyStackException
• Applications: Page-visited history in a Web browser, Undo sequence in a text editor

Array-based stack

• A simple way of implementing the Stack ADT uses an array
• We add elements from left to right
• A variable t keeps track of the index of the top element (size is t+1)
• Throws errors when size exceeds array-size: FullStackException
• Limitations: The maximum size of the stack must be defined a priori and cannot be changed
• performance
  • Let n be the number of elements in the stack
  • The space used is O(n)
  • Each operation runs in time O(1)

Algorithm size()
  return t + 1

Algorithm push(o)
  if t = S.length − 1 then
    throw FullStackException
  else
    t ← t + 1
    S[t] ← o

Algorithm pop()
  if isEmpty() then
    throw EmptyStackException
  else
    t ← t − 1
    return S[t + 1]

Growable Array-based Stack

• In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one
• How large should the new array be?
  • incremental strategy: increase the size by a constant c - Time O(n^2)
  • doubling strategy: double the size - Time O(n)

  Algorithm push(o)
    if t = S.length − 1 then
      A ← new array of size …
    for i ← 0 to t do
      A[i] ← S[i]
      S ← A
    t ← t + 1
    S[t] ← o

Code

package examples;

import java.util.Arrays;

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

    // instance variables
    private E [] stor = (E[]) new Object[1];
    private int ptr; // points to the next insertion position

    private void expand(){
        stor = Arrays.copyOf(stor,stor.length*2);
    }


    @Override
    public void push(E o) {
        if (ptr==stor.length) expand();
        stor[ptr++]=o;
    }

    @Override
    public E pop() {
        try {
            return stor[--ptr];
        } catch (IndexOutOfBoundsException e) {
            throw new RuntimeException("stack underflow");
        }
    }

    @Override
    public E top() {
        try {
            return stor[ptr-1];
        } catch (IndexOutOfBoundsException e) {
            throw new RuntimeException("stack underflow");
        }
    }

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

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

    static public void main(String[] argv){
        MyStack<String> st = new MyStack();
        st.push("hans");
        st.push("Beat");
        st.push("Ida");
        st.push("Susi");
        st.pop();
        st.pop();
        st.pop();
        st.pop();
        String last = st.pop();
        System.out.println(last);
    }

}