Queues

Let’s consider a queue implementation by looking at a corresponding API and the operations that a queue would include.

QueueOfStrings() // Create an empty queue
void enqueue(String item) // insert a new string onto queue
String dequeue() //remove and return the string LEAST recently added
boolean isEmpty() //is the queue empty
int size() //number of strings on the queue

Just like stacks, we have similar operations of adding and removing; however, the naming conventions and semantics are important to note. Similar to queues in real life, adding an item to a queue puts it as the newest addition, and removing an item from a queue removes the item that was least recently added. To put this into a real-life example:

If we had a queue towards a nightclub door, new patrons arriving would enqueue, and the patrons at the front of the line who were waiting the longest would dequeue after going in.

Implementing a Queue with a LinkedList

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;
    }
## Implementing a Queue with a Resizing Array
Similar in concept to the resizing array in a stack, to simplify the process we would essentially break down the process with the below pseudo code:

1. use an array to store our items lets say `q[]`
2. our `enqueue()` function would add new items at `q[tail]`
3. our `dequeue()` function would remove items from `q[head]`
4. We would update our `head` and `tail` according to a modulo of our `capacity`
5. that would in turn be amortizing and adding the resizing array to our client.
Similar in concept to the resizing array in a stack to simplify the process we would essentially break down the process with the bellow pseudo code.

1. use an array to store our items lets say `q[]`
2. our `enqueue()` function would add new items at `q[tail]`
3. our `dequeue()` function would remove items from `q[head]`
4. We would update our `head` and `tail` according to a modulo of our `capacity`
5. that would in turn be amortizing and adding the resizing array to our client.