Stacks and Queues

Data structures are ways to organize data and make it available. Algorithms are instructions to solve in a certain amount of time a certain problem. Abstract data types (ADT) are models of a data structure specifying the type of data and operations to perform on. In Java these are often interfaces.

Stacks

A stack is a relatively simple data structure storing data following the Last-In-First-Out (LIFO) principle. Compare with order stack in restaurant. Fundamental operations of a stack are

  • push(e) : add element to stack
  • pop(): remove last element from stack and return

Further important operations are

  • size()
  • isEmpty()
  • top(): return last element from stack without removal.

Implementation of the stack ADT works in two steps. First define interface with methods, then make concrete implementation of this interface. This then becomes the concrete data type.

Queue

A queue is a direct neighbor of the stack. It works following the First-In-First-Out (FIFO) principle. It needs to implement these operations

  • enqueue(e): add element to queue
  • dequeue(): remove first element from queue and return

Different from stacks, we cannot simply remove an element from the queue as this is by definition the first element and all other elements would need to be moved element by element to the first element. Instead, we can implement queue as an circular array with moving upward the beginning index (b) with every dequeueing and moving upward the last index (l) with every enqueueing. In Java, the operation would look like this.


int nMax = 1000;
ArrayList<E> queue = new ArrayList<E>(nMax);
int b = 0;
int l = 0;

public void size(){
  return (nMax - b + l);
}

public void isEmpty(){
  return (l == b);
}

public void front(){
  if (l != b){
    return queue[b]; 
  }
}

public void enqueue(E e){
  if (size() < nMax -1 ){
    queue[l] = e; 
    l = (l + 1) % nMax; // modulo needed for starting from index 0 after nMax is reached.
  }
}

public void dequeue(){
if (b != l){
  E temp = queue[b];
  queue[b] = null;
  f = (f +1) % nMax
  return temp;
} 
}

Linked lists

Linked lists are ADTs that do not have the restriction to specify the number of elements at forehand. There is one head element and it has an attribute next which points to the following element. If that is null, there is no following element.

A linked list builds upon a node class containing a reference to the object it is is associated with and a reference to the next node.


public class Node<E>{
  private E element;
  private Node<E> next;

public Node(E element, Node next){}
public E getElement();
public Node<E> getNext();
public void setElement(E e);
public void setNext(Node<E> l);
}

public class LStack<E> implements Stack{
  private int size;
  private Node<E> head = null;

  public void push (E element){
    Node<E> temp = new Node(element, head);
    head = temp;
    size ++;
  }

  public E pop(){
    if (this.isEmpty()){throw new Exception();}
    Node<E> oldhead = head;
    head = head.getNext();
    oldhead.setNext(null);
    size --;
    return oldhead.getElement();
  }

}

For a queue, we do also need to add a tail attribute as running through the whole list is an expensive procedure.


public void enqueue(E element){
  Node<E> temp = new Node<E>(element, null);

  if(head == null){
    head = temp;
    tail = temp;

  } else{
    tail.setNext(temp);
    tail = temp;
  }
}

public E dequeue(){
if (this.isEmpty()){throw new Exception();}
    Node<E> oldhead = head;
    head = head.getNext();
    oldhead.setNext(null);
    size --;
    return oldhead.getElement();
  }

Sortability

Some of the interfaces provided by the Collection Framework allow

Iterator