This post shows you how to implement a Stack and a Queue in Java. It might be handy in interviews ;)
Implementing a Stack:A stack uses LIFO (last-in first-out) ordering. Think of a stack of dinner plates. It provides constant time adds and removes. Sample code:
public class Stack<E> { private static class StackItem<E> { final E data; StackItem<E> next; public StackItem(final E data) { this.data = data; } } private StackItem<E> top; public boolean isEmpty() { return top == null; } public void push(final E e) { final StackItem<E> toAdd = new StackItem<>(e); toAdd.next = top; top = toAdd; } public E pop() { if (isEmpty()) { throw new NoSuchElementException("Stack is empty"); } final E data = top.data; top = top.next; return data; } public E peek() { if (isEmpty()) { throw new NoSuchElementException("Stack is empty"); } return top.data; } }Implementing a Queue:
A queue uses FIFO (first-in first-out) ordering. Sample code:
public class Queue<E> { private static class QueueItem<E> { final E data; QueueItem<E> next; public QueueItem(final E data) { this.data = data; } } private QueueItem<E> first; private QueueItem<E> last; public boolean isEmpty() { return first == null; } public void add(final E e) { final QueueItem<E> toAdd = new QueueItem<>(e); if (last != null) { last.next = toAdd; } last = toAdd; if (first == null) { first = last; } } public E remove() { if (isEmpty()) { throw new NoSuchElementException("Queue is empty"); } final E data = first.data; first = first.next; if (first == null) { last = null; } return data; } public E peek() { if (isEmpty()) { throw new NoSuchElementException("Queue is empty"); } return first.data; } }