Stack

imagen

A stack is exactly what is sounds like, a last in first out data structure (LIFO). Whatever the most recent item added will be the first one removed.

It typically consists of 4 operations:

pop(): returns and removes the item from the top of the stack
push(item): adds the item to the top of the stack
peek(): return the top of the stack
isEmpty(): return true if the stack is empty

The benefit of using a stack versus an array is that it allows constant time for adds and removes, as it doesn't require shifting elements around.

Here is some simple code on a generic implementation of a stack:

public class Stack <T> {

    // internal class only used by the stack
    private static class StackNode<T> {
        private T data;
        private StackNode<T> next;

        public StackNode(T data) {
            this.data = data;
        }
    }

    private StackNode<T> top;

    public T pop() {
        if (top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        StackNode<T> t = new StackNode<>(item);
        top = t;
        t.next = top;
    }

    public T peek() {
        if (top == null) throw new EmptyStackException();
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

Bear in mind when you are writing recursive algorithms that Stacks are particularly useful. Sometimes you need to push temporary data onto a stack as you recurse, but then remove them as you backtrack (for example, because the recursive check failed). A stack offers an intuitive way to do this.

A Stack is also really useful if you want to implement a recursive algorithm iteratively.

Queue

imagen

Very similar to a Stack, but the order is FIFO, first in first out. Imagine a line or a queue at a ticket stand, the items are removed from the data structure in the same order as they are added.

It uses the following functions:

add(item): adds to the end of the queue
remove(): returns and first item of the queue
peek(): returns the top of the queue
isEmpty(): return true if the queue is empty

public class Queue<T> {
    private static class QueueNode<T> {
        private T data;
        private QueueNode<T> next;
        public QueueNode(T data) {
            this.data = data;
        }
    }

    private QueueNode<T> first = null;
    private QueueNode<T> last = null;

    public void add(T item) {
        QueueNode<T> t = new QueueNode<>(item);
        if (last != null) last.next = t;
        last = t;
        if (first == null) first = last;
    }

    public T remove() {
        if (first == null) throw new NoSuchElementException();
        T data = first.data;
        first = first.next;
        if (first == null) last = null;
        return data;
    }

    public T peek() {
        if (first == null) throw new NoSuchElementException();
        return first.data;
    }

    public boolean isEmpty() {
        return first == null;
    }
}

To give you some context, Queues are often used in implementing caches or Breadth First Search (BFS).

In BFS for instance, we use a queue to store the list of nodes that we need to process. Each time we process a node we add its adjacent nodes to the back of the queue. This allows us to process the nodes in the order in which they are viewed.

Kodr

Stack & Queues

Stack

Queue