This post is a continuation of my series on data structures. We will be covering the queue data structure. For all of these examples of how to implement data structures, I recommend you use what's provided in your language framework when available.

We will go over what it is, when you should use it, its basic operations, and the implementation.

If you don't care about any of the explanation, and are only looking for code snippets, that's cool too. You can find the full implementation in my Github repository.

What Is a Queue Data Structure?

A Queue is a collection that keeps items in a sequence and abides by the first in, first out ( FIFO ) rule. Regardless of when elements are inserted, the oldest element is removed first.

You can visualize this by thinking of standing in line at the grocery store. The person who was first in line is the first one to checkout.

When Should I Use The Queue Data Structure?

You should use a queue data structure whenever you want to handle items in a first in, first out ( FIFO ) order. This could be things such as incoming events and requests, or messages sent to a user.

What Are the Basic Operations of a Queue?

The two main operations of a queue are Enqueue and Dequeue. It may contain operations for returning the queue size, an "is empty" check, and an operation for returning (but not removing) the first element.

All of these operations run in O(1) (constant) time.

Queue Enqueue Function

Enqueue is the insert functionality of the queue. It adds an element to the end of the collection.

If the head node is null, we assign the newly created node to it and the tail. Otherwise, we point the "Next" reference to the newly created node. Then we set the newly created node to be the tail.

{
  var temp = new QueueNode(element); 

  if(head == null)
    head = tail = temp;
  else
  {
    tail.Next = temp;
    tail = temp;
  }
}

Queue Dequeue Function

Dequeue is the remove functionality of the queue. If the queue is empty, we throw an exception.

Once we confirm the queue is not empty, we store the value of the head node of the queue to the temp variable. We then make the second node of the queue the new "head" of the queue. Finally return the value stored in temp.

public T Dequeue()
{
  if(head == null)
    throw new Exception("Queue Empty");

  var temp = head.Element;
  head = (QueueNode)head.Next;

  return temp;
}

How Do I Implementation a Queue?

There are two different ways of implementing queues. One implementation uses an array to hold the elements, while the other uses a linked list. Each version has the operations for enqueue and dequeue.

You can see examples of both below. The array based version takes an "size" parameter which determines the size of the queue. The enqueue operation for the array based implementation has an additional check to confirm the backing array has space for the new element.

public class Queue<T>;
{

  private T[] queue;

  private int head = 0;
  private int tail = 0;
  private int size;

  public Queue(int size = 10)
  {
    this.size = size;
    queue = new T[size];
  }

  //O(1)
  public void Enqueue(T element)
  {
    if (tail &gt; size)
      throw new Exception("Queue Overflow");

    queue[tail] = element;
    if (tail == size)
      tail = 1;
    else
      tail++;
  }

  //O(1)
  public T Dequeue()
  {
    T element = queue[head];
    if (head == size)
      head = 1;
    else
      head++;

    return element;
  }
}

Side Note: There is a way to create an array based queue that doesn't run into the size limitation issue. You would need to check on enqueue that the queue has space. If it does not, you can create a new array of larger size (usually double) and copy the elements over. This isn't the most efficient, and will have an effect on Big O complexity. But it gets the job done.

public class Queue<T>
{
    private Node head;
    private Node tail;

    public void Enqueue(T element)
    {
      var temp = new Node(element); 

      if(head == null)
        head = tail = temp;
      else
      {
        tail.Next = temp;
        tail = temp;
      }
    }

    public T Dequeue()
    {
      if(head == null)
        throw new Exception("Queue Empty");

      var temp = head.Element;
      head = (Node)head.Next;

      return temp;
    }
  }
}

Both implementations use generics so you can store any data type in the queue.

Final Thoughts

As I mentioned in my article on how to implement at stack, if you should use the queue provided with whatever framework you are using.

But I hope you found this to be a helpful example of seeing how queues work under the hood. Please share your thoughts below. And feel free to share this post with others!