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
- Start
- Declare Node structure with value and pointer to next node
- Create methods: enqueue(value) for adding elements, dequeue() for removing elements
- Create a front and rear pointers initialized to NULL
- 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