In an earlier post, we saw implementation of Queues using arrays. Now, we will use a Linked List to store the elements instead of an array. Since we are all linked list champs by now, we already know how to go about building a linked list given an input set of elements - create nodes that contain our elements and join the nodes using next pointers.

We will also use this example to introduce the notion of a friend class in C++.

A friend class F is a C++ class that can access private and protected members of another class A in which F is declared as friend. Here, a Queue class (F) may be allowed to access private members of a Node class (A).

class Node {
  private:
    int data;
    Node *next;
    friend class Queue;
};

class Queue {
  private:
    Node *front, *rear;
  public:
    Queue ();
    void enqueue (int item);
    bool is_empty ();
    int dequeue ();
};

Queue::Queue () {
  this->front = NULL;
  this->rear = NULL;
}

There is also a notion of friend function, very similar to friend class:

A friend function f can be used to access private and protected members of a class A and it can be either:

  • a method of a class A
  • a global function

In the following post, we will see how to implement the methods enqueue() and dequeue() for the Queue class above.