Queues - Eishaaya/GMRDataStructuresTest GitHub Wiki

What is a Queue?

A queue is a data structure that has a unique characteristic called first-in-first-out (FIFO). The first object to enter the queue is the first object that is accessible. To access that last object, you would have to dequeue all of the objects before it. To add an object to the queue, you would have to enqueue it to the back of the queue.

To maintain the FIFO ordering, data can only be added to the back of the queue and accessed from the front of the queue, often referred to as enqueueing and dequeuing, respectively. That is really all that the queue entails.

Like the Stack class, the Queue class can be implemented as a linked-list backed queue, or an array-backed queue. For the array, we just need two integer indices to represent the front and end of the queue.

Linked-List backed Queue:

public class Queue<T>
{
  public int Count { get; private set; }
  private LinkedList<T> data;

  public Queue() { ... }
  public void Enqueue(T value) { ... }
  public T Dequeue() { ... }
  public T Peek() { ... }

  // Optional Functions
  public bool IsEmpty() { ... } 
  public void Clear() { ... }
}

Array backed Queue:

public class Queue<T>
{
  public int Count { get; private set; }
  private T[] data;
  private int head;
  private int tail;

  public Queue() { ... }
  public void Enqueue(T value) { ... }
  public T Dequeue() { ... }
  public T Peek() { ... }
  private void Resize(int size) { ... }

  // Optional Functions
  public bool IsEmpty() { ... } 
  public void Clear() { ... }
}

Implementation Guide

Enqueue

Always add elements to the tail of the queue:

  • Linked-List: Add to the tail of the list.
  • Array: Add at the tail index of the list. If the index must go past the end of the array, use modulo or an if statement to wrap the index back to the front of the array. If the tail reaches the head, then all indices of the array are filled with values; double the size of the array with the Resize function.

Dequeue

Always remove elements from the head of the queue:

  • Linked-List: Remove and return the value at the head of the list.
  • Array: There is still no need to remove the value from the array. Just move the head index up. If the head index must go past the end of the array, use modulo or an if statement to wrap the index back to the front of the array. If the count of in-use elements reaches 1/4 the size of the array, call the Resize function to reduce the size of the array to 1/2 in order to save space. Just don't copy the values we didn't clear earlier!

Peek

Return the value at the head of the queue.

Assignments

Easy:

  • Array Backed Queue
    • Implement a queue using an array to store the values instead of a linked list.

Hard:

  • Post Office Simulator
    • Allow a person to enqueue in line at any point in time and watch in real-time as each person is served and where they are at, being served in order
    • Have a random amount of people come to the post office every minute waiting in a queue
    • Have a random amount of items that each person has, taking a random amount of seconds to process
    • Have a certain amount of items that can be queue before packages must be delivered at the post office, halting the entire line until delivery is finished
    • Have a random processing speed per Post office employee with a certain queue for their packages before they must take a break

References

<-- Previous | Next -->