Stack & Queues
Stack
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
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.