Queue

Queue is a simple data structure serves collection of elements with 2 main operations (enqueue and dequeue). The order of each element is added or removed from a stack is referred by FIFO (First In First Out).

Array-Based Implementation

template <typename E>
class ArrayQueue
{
  enum
  {
    DEF_CAPACITY = 100
  };

public:
  ArrayQueue(int cap = DEF_CAPACITY)
  {
    n = f = r = 0;
    capacity = cap;
    arr = new E[cap];
  }
  int size() const
  {
    return n;
  }
  bool empty() const
  {
    return n == 0;
  }
  const E &front() const
  {
    if (empty())
    {
      throw runtime_error("Front of empty queue");
    }
    return arr[f];
  }
  void enqueue(const E &e)
  { // push back
    if (r == capacity)
    {
      throw runtime_error("Push to full queue");
    }
    arr[r++] = e;
    n++;
    r %= capacity;
  }
  void dequeue()
  { // pop front
    if (empty())
    {
      throw runtime_error("Pop from empty queue");
    }
    f++;
    f %= capacity;
    n--;
  }

private:
  E *arr;
  int capacity;
  int n; // current no. of elements
  int f; // index of the front
  int r; // index of the rear
};

Implementing Queue with Circularly Linked List

We’ll use Circularly linked list implemented before. this is how we can do the enqueue and dequeue with it:

enqueue

dequeue

LinkedQueue

template <typename E>
class LinkedQueue
{
public:
  LinkedQueue()
  {
    n = 0;
    C();
  }
  int size() const
  {
    return n;
  }
  bool empty() const
  {
    return n == 0;
  }
  const E &front() const
  {
    if (empty())
      throw(runtime_error("Front of empty queue"));
    return C.front();
  }
  void enqueue(const E &e)
  {
    C.add(e);
    C.advance();
    n++;
  }
  void dequeue()
  {
    if (empty())
      throw(runtime_error("Dequeue from empty queue"));
    C.remove();
    n--;
  }

private:
  CircleList<E> C;
  int n;
};

Double-Ended Queue (Deque)

Generalizes a Queue as elements can be added or removed from either the front (head) or back(tail).

Using doubly linked list

This ADT can very easily be implemented using a doubly linked list. You should test this implementation with this problem on LeetCode

template <typename E>
class LinkedDeque
{
public:
  LinkedDeque()
  {
    n = 0;
  }
  int size() const
  {
    return n;
  }
  bool empty() const
  {
    return n == 0;
  }
  const E &front() const
  {
    if (empty())
      throw(runtime_error("Front of empty deque"));
    return D.front();
  }
  const E &back() const
  {
    if (empty())
      throw(runtime_error("Back of empty deque"));
    return D.back();
  }
  void insertFront(const E &e)
  {
    D.addFront(e);
    n++;
  }
  void insertBack(const E &e)
  {
    D.addBack(e);
    n++;
  }
  void removeFront()
  {
    if (empty())
      throw(runtime_error("Remove front of empty deque"));
    D.removeFront();
    n--;
  }
  void removeBack()
  {
    if (empty())
      throw(runtime_error("Remove back of empty deque"));
    D.removeBack();
    n--;
  }

private:
  DLinkedList<E> D;
  int n;
};

Using circular array

The most important key-point is how to move the front and rear when addBack or addFront.

I’ll add more features like dynamic size and index accessing. You should be familiar with vector (dynamic size array).

You should test this implementation with this problem on LeetCode

template <typename E>
class CircularVector
{
public:
  CircularVector()
  {
    capacity = n = 0;
    f = r = -1;
    arr = NULL;
  }
  int size() const
  {
    return n;
  }
  bool empty() const
  {
    return n == 0;
  }
  E &operator[](int i)
  {
    return arr[(f + i) % capacity];
  }
  E &at(int i)
  {
    if (i < 0 || i >= n)
    {
      throw runtime_error("Illegal index in function at()");
    }
    return arr[(f + i) % capacity];
  }
  E &front()
  {
    if (empty())
    {
      throw runtime_error("front of empty circular vector");
    }
    return arr[f];
  }
  E &back()
  {
    if (empty())
    {
      throw runtime_error("back of empty circular vector");
    }
    return arr[r];
  }
  void erase(int idx)
  {
    if (empty())
    {
      throw runtime_error("erase from empty CircularArray");
    }
    int cur = (idx + f) % capacity;
    for (int i = cur; i != r; i = (i + 1) % capacity)
    {
      arr[i] = arr[(i + 1) % capacity];
    }
    r = (r - 1 + capacity) % capacity;
    n--;
  }
  void removeFront()
  {
    if (empty())
    {
      throw runtime_error("erase from empty circular array");
    }
    f = (f + 1) % capacity;
    n--;
  }
  void removeBack()
  {
    if (empty())
    {
      throw runtime_error("erase from empty circular array");
    }
    r = (r - 1 + capacity) % capacity;
    n--;
  }
  void insert(int idx, const E &e) // inserted element will be at idx
  {
    if (n >= capacity)
    {
      reserve(max(1, 2 * capacity)); // 1 because capacity will be initially 0
    }
    if (empty())
    {
      f = r = 0;
      arr[r] = e;
      n++;
      return;
    }
    for (int i = (r + 1) % capacity; i != (idx + f) % capacity; i = (i - 1 + capacity) % capacity)
    {
      arr[i] = arr[(i - 1 + capacity) % capacity];
    }
    arr[(idx + f) % capacity] = e;
    r = (r + 1) % capacity;
    n++;
  }
  void insertFront(const E &e)
  {
    if (n >= capacity)
    {
      reserve(max(1, 2 * capacity)); // 1 because capacity will be initially 0
    }
    if (empty())
    {
      f = r = 0;
      arr[f] = e;
      n++;
      return;
    }
    f = (f - 1 + capacity) % capacity;
    arr[f] = e;
    n++;
  }
  void insertBack(const E &e)
  {
    if (n >= capacity)
    {
      reserve(max(1, 2 * capacity)); // 1 because capacity will be initially 0
    }
    if (empty())
    {
      f = r = 0;
      arr[f] = e;
      n++;
      return;
    }
    r = (r + 1) % capacity;
    arr[r] = e;
    n++;
  }
  void reserve(int N)
  {
    if (capacity >= N)
      return;
    E *newArray = new E[N];
    for (int i = 0; i <= r; i++)
    {
      newArray[i] = arr[i];
    }
    int nf = N;
    for (int i = N - 1, j = n - 1; f > r && j >= f; i--, j--)
    {
      newArray[i] = arr[j];
      nf--;
    }
    if (f > r)
      f = nf;
    if (arr != NULL)
      delete[] arr;
    arr = newArray;
    capacity = N;
  }

private:
  E *arr;
  int capacity; // current array size
  int n;        // no. of elements
  int f;        // front
  int r;        // rear
};

Images from DSA in C++ book.