Implementing a Queue - Linked List

Similar to how we implemented a stack using linked lists we will now implement a queue using the same technique. The difference being we will need to maintain two pointers due to the enqueue and dequeue operations needing to maintain pointers for the “front” and “end” of the list.

Implementing Enqueue and Dequeue

Assume the following inner class structure

private class Node{
  String item;
  Node next;
}

Dequeue

1. Save item to return

String item = first.item;

2. Delete first node

first = first.next;

3. Return saved item

return item;

Enqueue

1. Save pointer to current last node

Node oldLast = last;

2. Create a new node to be the new last

last = new Node();

3. Set the item and next for the new last node

last.item = item;
last.next = null;

4. Handle empty queue special case:

if (isEmpty())
  {
    first = last;
  }

5. Link the previous last node to the new last node (if not empty):

else { oldLast.next = last; }

Full Code

public class LinkedQueueOfStrings
{
  private Node first , last;

  private class Node
  {
    String item;
    Node next;
  }

  public boolean isEmpty()
  { return first == null; }

  public void enqueue(String item)
  {
    Node oldLast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    //special cases for empty queue
    if(isEmpty())
    {
      first = last;
    }
    else
    {
      oldLast.next = last;
    }
  }

  public String dequeue()
  {
    String item = first.item;
    first = first.next;
    //special cases for empty queue
    if(isEmpty())
    {
      last = null;
    }
    return item;
  }

}