Implementation of Queue Using Linked List

To understand the implementation of a queue using a linked list using C++

Objective

To understand the implementation of a queue using a linked list using C++

#include <iostream>
using namespace std;

// A linked list (LL) node to store a queue entry
class Node {
    public:
        int key;
        Node* next;
};

// The queue, front stores the front node of LL and rear stores the last node of LL
class Queue {
    public:
        Node *front, *rear;
        Queue() {
            this->front = this->rear = NULL;
        }
        void enqueue(int key);
        void dequeue();
};

void Queue::enqueue(int key) {
    // Create a new LL node
    Node* temp = new Node();
    temp->key = key;
    temp->next = NULL;

    // If queue is empty, then new node is front and rear both
    if (this->rear == NULL) {
        this->front = this->rear = temp;
        return;
    }

    // Add the new node at the end of queue and change rear
    this->rear->next = temp;
    this->rear = temp;
}

void Queue::dequeue() {
    // If queue is empty, return NULL
    if (this->front == NULL) {
        return;
    }

    // Store previous front and move front one node ahead
    Node* temp = this->front;
    this->front = this->front->next;

    // If front becomes NULL, then change rear also as NULL
    if (this->front == NULL) {
        this->rear = NULL;
    }
    delete (temp);
}

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.dequeue();
    q.dequeue();
    q.dequeue();
    return 0;
}

Discussion of Algorithms

1. Start
2. Declare Node structure with value and pointer to next node
3. Create methods: enqueue(value) for adding elements, dequeue() for removing elements
4. Create a front and rear pointers initialized to NULL
5. End

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |           Start                  |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      Declare Queue object q      |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Enqueue operations       |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Dequeue operations       |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |             |                    |
   +----------------------------------+

Tabular Dry Run

Enqueue | Dequeue
   1    |   
   2    |   
   3    |   
        |   1
        |   2
        |   3

Results/Output

Enqueue: 1
Enqueue: 2
Enqueue: 3
Dequeue: 1
Dequeue: 2
Dequeue: 3