Scientific Programming II

ModSim

Stacks

What is a stack?

A stack is a data structure in which insertions and deletions occur only at the beginning; the topmost value is the last value in the stack. As such, stacks are considered FILO (first in, last out) data structures. Duplicate entries are allowed in stacks, unlike sets.

In this unit we will also begin using generics in earnest! Generics are one of Java's most powerful features, as they allow you to write dynamic data structures that hold any other type. We got a peek (no pun intended, see below) at generics with Linked Lists, but from now on all of our data structures will be generic.

Stacks are quinessentially Linked Lists with four methods:

• public void push(T val) - Add a value to the Stack
• public T pop() - Remove a value from the Stack
• public T peek() - Get the topmost value without removing it (see the pun?)
• public boolean isEmpty() - Test if the Stack is empty
• public String toString() - Convert the Stack into a String
  

Stacks are some of the most important data structures in computer science. Imagine you're editing text in Pages or Word. Whenever you make a mistake (and, you do), the 'Undo' and 'Redo' functions are simply stack operations! All of your editing commands are pushed onto the stack, and then when you call 'Undo' they are popped.

Additionally, stacks make it easy to test for balanced parentheses. Take the following examples:

( ( ) )
( ) ) (

We know instrisically that the upper set of parens are balanced, while the lower set are not. However, if we simply count the number of left and right parens, we would say that both sets are balanced. If, however, we employ some Stacks we can eliminate this problem!

public class ParenBalance
{
    public static void main(String[] args)
    {
        String one = "(())";
        String two = "())(";

        if (parenCheck(one)) {
            System.out.println("YAY");
        }

        if (parenCheck(two)) {
            System.out.println("BOO");
        }
    }

    public static boolean parenCheck(String parens)
    {
        // This stack will hold characters as we need them.
        Stack<Character> stack = new Stack<>();
        // We'll be returning this value.
        boolean balanced = true;
        // Converting the String to a char array will simplify traversing it.
        char[] charArr = parens.toCharArray();

        // Traversing the array:
        // 1. If we encounter a left paren, push it to the stack
        // 2. If we encounter a right paren, pop the stack (those parens were balanced)
        //    a. If the stack is ever empty when we encounter a right parens, we aren't balanced.
        for (int i = 0; i < charArr.length; i++) {
            Character symbol = charArr[i];
            if (symbol == '(') {
                stack.push(symbol);
            } else {
                if (stack.isEmpty()) balanced = false;
                else stack.pop();
            }
        }

        return balanced && stack.isEmpty();
    }
}

Additionally, stacks allow easy conversion from decimal to binary formats. Granted, there are much more efficient ways to convert numbers, but this is guaranteed to work no matter the number (negative can be simulated by prepending an active bit to the end to account for the sign bit).

public class DecToBin
{
    public static void main(String[] args)
    {
        System.out.println(toBin(233));
    }

    public static String toBin(int num)
    {
        Stack<Integer> stack = new Stack<>();

        while (num > 0) {
            stack.push(num % 2);
            num /= 2;
        }

        StringBuilder retString = new StringBuilder();
        while (!stack.isEmpty()) {
            retString.append(stack.pop().getData());
        }
        return retString.toString();
    }
}