2. Stacks

A stack organizes entries according to the order in which they were added, so instead of the queue's FIFO, a stack is LIFO, last-in first-out. Think of a bowls stack on top of each other, a stack ADT can represent that ordering. Stacks can be used for a lot of things, however, they are especially useful when check if delimiters are balanced. Below is an example of how a stack works with some pushes and pops.

Abstract Data Type: Stack

Data:

• A collection of objects in reverse chronological order with the same data type.

Pseudocode	UML	Description
push(newEntry)	+push(newEntry: T): void	Adds a new entry to the top of the stack.
pop()	+pop(): T	Removes and returns the top entry.
peek()	+peek(): T	Returns the top entry and doesn't change the stack.
isEmpty()	+isEmpty(): boolean	Dectects whether the stack is empty.
clear()	+clear(): void	Removes all emtries from the stack.

Interface of the ADT Stack

public interface StackInterface<T> {
    /** Adds a new entry to the top of this stack.
    @param newEntry An object to be added to the stack. */
    public void push(T newEntry);

    /** Removes and returns this stack's top entry.
    @return The object at the top of the stack.
    @throws EmptyStackException if the stack is empty before the operation. */
    public T pop() throws EmptyStackException;

    /** Retrieves this stack's top entry.
    @return The object at the top of the stack.
    @throws EmptyStackException if the stack is empty. */
    public T peek() throws EmptyStackException;

    /** Detects whether this stack is empty.
    @return True if the stack is empty. */
    public boolean isEmpty();

    /** Removes all entries from this stack. */
    public void clear();
}

A Linked-Based Implementation

Think of the stack as a chain, with the topmost node starting the chain then it progessively moves down said chain.

Pushing a new entry is as simple as setting the topmost node to the new entry node and have the new entry node point to the previous topmost node.

Poping a node, return the topmost node and point the topmost node to the second node.

public class LinkedStack<T> implements StackInterface<T> {
    private Node topNode;

    public LinkedStack() {
        this.topNode = null;
    }

    public void push(T newEntry) {
        this.topNode = new Node(newEntry, this.topNode); 
    }

    public T peek() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return topNode.getData();
        }
    }

    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T top = peek();
        this.topNode = this.topNode.getNextNode();
        return top;
    }

    public boolean isEmpty() {
        return this.topNode == null;
    }

    public void clear() {
        this.topNode = null;
    }

    private class Node {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return this.data;
        }

        public Node getNextNode() {
            return this.next;
        }
    }
}

An Array-Based Implementation

Like with most ADTs, you can use an array. Pushing, just add the new element to the topIndex. Popping, remove the topIndex and decrement by 1.

import java.util.Arrays;

public class ArrayStack<T> implements StackInterface<T> {
    private T[] stack;
    private int topIndex;

    public ArrayStack(int initialCapacity) {
        this.stack = (T[]) new Object[initialCapacity];
        this.topIndex = -1;
    }

    private void ensureCapacity() {
        if (this.topIndex == this.stack.length-1) {
            this.stack = Arrays.copyOf(this.stack, this.stack.length * 2);
        }
    }

    public void push(T newEntry) {
        ensureCapacity();
        this.topIndex++;
        this.stack[this.topIndex] = newEntry;
    }

    public T peek() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return this.stack[this.topIndex];
        }
    }

    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            T top = this.stack[this.topIndex];
            this.stack[this.topIndex--] = null;
            return top;
        }
    }

    public boolean isEmpty() {
        return this.topIndex < 0;
    }

    public void clear() {
        this.stack = (T[]) new Object[this.stack.length];
        this.topIndex = -1;
    }
}

A Vector-Based Implementation

Oh... you don't like the linked or array based implementations? Well, you can also use a vector-based implementation! This implementation generally follows the same style as the array implementation, but with more methods than painfully working with arrays.

import java.util.Vector;

public class VectorStack<T> implements StackInterface<T> {
    private Vector<T> stack;

    public VectorStack(int initialCapacity) {
        this.stack = new Vector<>(initialCapacity);
    }

    public void push(T newEntry) {
        this.stack.add(newEntry);
    }

    public T peek() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return this.stack.lastElement();
        }
    }

    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return this.stack.remove(this.stack.size() - 1);
        }
    }

    public boolean isEmpty() {
        return this.stack.isEmpty();
    }

    public void clear() {
        this.stack.clear();
    }
}

Next Page →