Queue Implementation Using Linked List

Implementing queue operations using a linked list

Implementation

1

Enqueue Operation

  • Create a new node with the given data.
  • Check if the queue is empty:
    • If head is NULL, set both head and tail to point to the newly created node.
    • Otherwise, link the tail node's next pointer to the new node, then update tail to point to the new node.
  • Increment the size of the queue by 1.
2

Dequeue Operation

  • Check if the queue is empty:
    • If head is NULL, print an error message ("Queue is empty") and return.
  • Remove the front node:
    • Store the current head in a temporary variable (oldHead).
    • Update head to point to the next node (head = head->next).
    • If the new head is NULL, set tail to NULL (indicating the queue is now empty).
  • Delete the oldHead node to free memory.
  • Decrement the size of the queue by 1.
3

IsEmpty Operation

  • Check if the queue is empty:
    • If head is NULL, return true (queue is empty).
    • Otherwise, return false.
4

Front Operation

  • Check if the queue is empty:
    • If head is NULL, print an error message ("Queue is empty") and return -1 (indicating an invalid front element).
  • Return the data of the node at the front (head->data).

Coding Implementation

//queueusinglinkedlist.cpp
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *next;
Node(int data) {
    this->data = data;
    this->next = NULL;
}
};

class Queue {
Node *head;
Node *tail;
int size;

public:
Queue() {
    this->head = NULL;
    this->tail = NULL;
    this->size = 0;
}

void enqueue(int data) {
    Node *temp = new Node(data);
    if (this->head == NULL) { 
        this->head = temp;
        this->tail = temp;
    } else { 
        this->tail->next = temp;
        this->tail = temp;
    }
    this->size++;
}

void dequeue() {
    if (this->head == NULL) { 
        cout << "Queue is empty, cannot dequeue." << endl;
        return;
    }
    Node *oldHead = this->head;
    this->head = this->head->next;
    if (this->head == NULL) { 
        this->tail = NULL;
    }
    delete oldHead;
    this->size--;
}

int getSize() {
    return this->size;
}

bool isEmpty() {
    return this->head == NULL;
}

int getFront() {
    if (this->head == NULL) {
        cout << "Queue is empty, no front element." << endl;
        return -1;
    }
    return this->head->data;
}
};

int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);

while (!q.isEmpty()) {
    cout << q.getFront() << " ";
    q.dequeue();
}
// 10 20 30 40 50

}

Comparison of Queue Implementation Using Array and Linked List

FeatureArrayLinked List
Memory AllocationRequires a contiguous block of memory.Uses non-contiguous memory; nodes allocated dynamically.
SizeFixed size (needs resizing for dynamic growth).Dynamic size, no resizing needed.
Memory EfficiencyCan waste space if resized or over-allocated.Allocates memory exactly as needed.
Enqueue Operation (Insert)O(1), unless resizing is needed.O(1), always efficient.
Dequeue Operation (Delete)O(1), straightforward.O(1), straightforward.
Access to ElementsDirect access to elements by index.Linear access, must traverse from the front.
Overflow ConditionOccurs when the array is full.No overflow, can grow dynamically.
Underflow ConditionOccurs when trying to dequeue from an empty queue.Occurs when trying to dequeue from an empty queue.