queue

Queue Data Structure

A queue is another list-type data structure and (in this case) an extension of a doubly linked list. The defining trait of a queue is that insertion only happens at the end (last node) and deletion only happens at the front (first node). The queue employs a First In First Out (FIFO) structure, meaning the order that nodes are enqueued will be the order that they are read from. This is the opposite structure of a Stack. A practical use of a queue would be an application where people are waiting in line, because the people first in line are the first people to be served. Queues are also used when downloading multiple games at once, for example. Since games usually only download one at a time, they are put in a queue that downloads them one after the other.

Below is a basic implementation of a queue in C++. We implement it using a doubly linked list and with three main functions:

Enqueue - Add a node to the end of the queue
Dequeue - Remove and return the node at the front of the queue
Peek - Return the value of the front node but don't remove it

using namespace std;

#include <iostream>

class Node {

public:

int value;

Node* next;

Node* previous;

Node(int v) {

value = v;

}

Node() {}

};

class Queue {

public:

Node* front;

Node* back;

Queue() {}

void enqueue(int value) {

Node* newNode = new Node(value);

if (front == NULL) {

front = newNode;

back = newNode;

}

else {

Node* current = front;

while (current->next != NULL) {

current = current->next;

}

newNode->previous = current;

current->next = newNode;

back = newNode;

}

Node* dequeue() {

if (front == NULL) {

throw "Queue is empty";

}

else {

front = front->next;

return front->previous;

}

Node* peek() {

if (front == NULL) {

throw "Queue is empty";

}

else {

return front;

}

};

void printQueueValues(Queue* qArg) {

if (qArg->front == NULL) {

throw "Queue is empty";

}

else {

Node* current = qArg->front;

while (current->next != NULL) {

cout << current->value << ", ";

current = current->next;

}

cout << current->value;

}

int main() {

Queue* q = new Queue();

q->enqueue(1);

q->enqueue(2);

q->enqueue(3);

q->enqueue(4);

cout << "Values after enqueuing:\n";

printQueueValues(q);

cout << "\nFirst dequeue value:\n";

cout << q->dequeue()->value;

cout << "\nQueue values after one dequeue:\n";

printQueueValues(q);

cout << "\nCurrent Peek value:\n";

cout << q->peek()->value;

}

Output:

Values after enqueuing:

1, 2, 3, 4

First dequeue value:

Queue values after one dequeue:

2, 3, 4

Current Peek value:

Click here to view the next section: Stacks