Stacks & Queues

Abstract Data Types (ADTs)

  • An ADT is an abstraction of a data structure
  • Specifies the operations performed on the data
  • Focus is on what the operation does, not how it does it
  • Expressed in java with an interface


  • A stack is a last in, first out data structure (LIFO)
  • Items can be pushed to or popped from the top
  • Example uses include:
    • Undo sequence in a text editor
    • Chain of method calls in the JVM (method stack)
    • As auxillary storage in multiple algorithms

The Stack ADT

The main operations are push() and pop(), but others are included for usefulness

public interface Stack<E>{
    int size();
    boolean isEmpty();
    E peek(); //returns the top element without popping it
    void push(E elem); //adds elem to the top of the stack
    E pop(); //removes the top stack item and returns it

Example Implementation

The implementation below uses an array to implement the interface above. Only the important methods are included, the rest are omitted for brevity.

public class ArrayStack<E> implements Stack<E>{
    private E[] elems;
    private int top = -1;

    public ArrayStack(int capacity){
        elems = (E[]) new Object[capacity];

    public E pop(){
        if (isEmpty()) return null;
        E t = elems[top];
        top = top-1;
        return t;
    public E push(){
        if (top == elems.length-1) throw new FullStackException; //cant push to full stack
        return elems[top];
  • Advantages
    • Performant, uses an array so directly indexes each element
    • space and each operation runs in time
  • Disadvantages
    • Limited by array max size
    • Trying to push to full stack throws an exception


  • Queues are a first in, first out (FIFO) data structure
  • Insertions are to the rear and removals are from the front
    • In contrast to stacks which are LIFO
  • Example uses:
    • Waiting list
    • Control access to shared resources (printer queue)
    • Round Robin Scheduling
      • A CPU has limited resources for running processes simultaneously
      • Allows for sharing of resources
      • Programs wait in the queue to take turns to execute
      • When done, move to the back of the queue again

The Queue ADT

public interface Queue<E>{
    int size();
    boolean isEmpty();
    E peek();
    void enqueue(E elem); //add to rear of queue
    E dequeue(); // pop from front of queue