3-12 The Dynamic Stack

You’ll recall in 3-9 we defined an interface for a stack abstract data type (ADT):

public interface StackADT<T> {
    // Adds one element to the top of the stack.
    public void push(T element);
    
    // Removes and returns a reference to the top element from the stack.
    public T pop();
    
    // Returns a reference to the top element, without removing it from the stack.
    public T peek();
    
    // Returns true if the stack contains no elements, false otherwise.
    public boolean isEmpty();
    
    // Returns the number of elements in the stack.
    public int size();
    
    // Clears all elements from the stack
    public void clear();
    
    // Returns a String representation of this stack.
    public String toString();
}

public interface StackADT<T> {

// Adds one element to the top of the stack.

public void push(T element);

// Removes and returns a reference to the top element from the stack.

public T pop();

// Returns a reference to the top element, without removing it from the stack.

public T peek();

// Returns true if the stack contains no elements, false otherwise.

public boolean isEmpty();

// Returns the number of elements in the stack.

public int size();

// Clears all elements from the stack

public void clear();

// Returns a String representation of this stack.

public String toString();

}

We will now create a DynamicStack class that will use (via composition) a LinkedList to manage the data. Our new class will implement the same StackADT interface (above) as our StaticStack class did – after all, the operations that a stack needs to support should not vary based on the hidden details of how the stack data will be managed.

Here is the DynamicStack code:

class DynamicStack<T> implements StackADT<T> {
    private LinkedList<T> myList;
    
    // Creates an empty stack (based on a linked list).
    public DynamicStack() {
        myList = new LinkedList<T>();
    }
    
    // Adds the specified element to the top of the stack
    public void push( T element ) {
        myList.addFirst( element );
    }
    
    // Removes the element from the top of the stack and returns a reference to it, or null (if empty).
    public T pop() {
        return myList.removeFirst(); 
    }
    
    // Returns a reference to the element at the top of the stack, or null (if empty).
    public T peek() {
        return myList.peekFirst();
    }
    
    // Returns true if the stack contains no elements, false otherwise.
    public boolean isEmpty() {
        return myList.isEmpty();
    }
    
    // Returns the number of elements in the stack.
    public int size() {
        return myList.size();
    }
    
    // Clears all elements from the stack
    public void clear() {
        myList.clear();
    }
    
    // Returns a String representation of the stack.
    public String toString() {
        return myList.toString();
    }
}

class DynamicStack<T> implements StackADT<T> {

private LinkedList<T> myList;

// Creates an empty stack (based on a linked list).

public DynamicStack() {

myList = new LinkedList<T>();

}

// Adds the specified element to the top of the stack

public void push( T element ) {

myList.addFirst( element );

}

// Removes the element from the top of the stack and returns a reference to it, or null (if empty).

public T pop() {

return myList.removeFirst();

}

// Returns a reference to the element at the top of the stack, or null (if empty).

public T peek() {

return myList.peekFirst();

}

// Returns true if the stack contains no elements, false otherwise.

public boolean isEmpty() {

return myList.isEmpty();

}

// Returns the number of elements in the stack.

public int size() {

return myList.size();

}

// Clears all elements from the stack

public void clear() {

myList.clear();

}

// Returns a String representation of the stack.

public String toString() {

return myList.toString();

}

On line 1 we are implementing the same StackADT interface that we used for our StaticStack in 3-9. Line 2 is encapsulating a private reference variable called myList that will refer to a LinkedList data structure. The empty linked list is actually instantiated in the DynamicStack() no-argument constructor. This is a great example of composition, where one class includes a reference to an object of another class.

After that you’ll notice that all of the stack methods we are defining are essentially one-liners calling their corresponding LinkedList methods. This is an excellent application of code reuse! However, you might wonder what the point of this is — why not just use a linked list? This is a good observation and yes, a linked list could be used in place of a stack.

BUT! What about the contains() method, or the addLast() or removeLast() methods that you added in 3-11? Strictly speaking, a stack is not supposed to have such methods but we would have no way to prevent them from being called if we used a linked list. By creating a DynamicStack class that implements only the methods defined by the StackADT interface, we get a stack data structure that supports exactly the methods we need, and nothing more.

To test the DynamicStack you can use the same code as our StaticStackTest code from 3-9, just change line 8 from:

       StaticStack<Integer> myStack = new StaticStack<>(3);

1	StaticStack<Integer> myStack = new StaticStack<>(3);

to:

       DynamicStack<Integer> myStack = new DynamicStack<>();

1	DynamicStack<Integer> myStack = new DynamicStack<>();

Notice that we no longer have to specify the size of the required stack anymore – it’s dynamic! Other than that, the rest of the code should work exactly the same because both the StaticStack and DynamicStack classes implement the same StackADT interface.

You Try!

Using the DynamicStack class, write a program that will ask the user to enter a mathematical expression as a string; for example: [ ( a + b ) – { c * ( b – a ) } ] and determine if the brackets are properly balanced or not. The supported bracket types should be: ( curved ), { curly }, and [ square ]. When checking an expression to determine if the brackets are balanced, each closing bracket ), }, or ] must be matched with the last non-matched open bracket (, {, or [. If they are a matching type, then the open bracket is considered matched. Here are some examples of balanced and unbalanced expressions:

a ( b ) // balanced
a [ b { c } d ] ( e ) // balanced
a { b { c } d ] e } // not balanced: ] does not match
a ( b [ c ] d // not balanced: missing closing )

Hint: To check if an expression is balanced, you scan it from left-to-right, storing each opening bracket in a stack. Each time a closing bracket is encountered, the top element in the stack is popped off and compared with the closing bracket. If they are matching types, scanning continues. If they do not match, the expression is not balanced and scanning ends. Once the entire expression is scanned, the stack is examined. If it is empty, the expression is balanced. If it is not empty, the expression is not balanced.