Rubenerd

In a previous post I implemented a basic stack in Java using linked lists. In this post I'll be looking at implementing a rudimentary queue.

Unlike a stack where the first object to be added is the last to be taken off which results in an inversion of order, objects in a queue are taken off in the same order they were added. In the context of a linked list, this means the objects are added to the head like a stack, but they're removed from the end instead.

In this case much of the code from the stack linked list is the same, all we need to change are the stack specific terms from pop and push to terms put and get, and change the remove method to pull objects from the end of the linked list not the beginning.

public class Queue {
  Node head;
  public Queue(Object payload) {
    if (payload)
      head = new Node(payload);
  }
  private class Node {
    Object payload;
    Node next;
    public Node(Object payload) {
      this.payload = payload;
    }
  }
}

Aside from being renamed from push, the put method is unchanged from the Stack method other than the name.

public void put(Object payload) {
  Node newNode = new Node(payload);
  if (head == null)
    head = newNode;
  else {
    newNode.next = head;
    head = newNode;
  }
}

The pop method is changed to get the last link list element not the first. We find this by traversing the linked list until we find a Node that has null as its next Node.

public Object get() {
  Node current = head;
  Node previous = head;
  while (current.next != null) {
    previous = current;
    current = current.next;
  }
  Object toReturn =  current.payload;
  previous.next = null;
  return toReturn;
}