Stack & Queue Using Linked Lists in C++

🔗 Stack and Queue Using Linked Lists in C++

In this tutorial, we’ll learn how to implement Stack and Queue using Linked Lists in C++. Linked lists provide dynamic memory allocation and are ideal when you don't know the size of the data structure beforehand.

📦 Stack Using Linked List (LIFO)

In Stack, the most recently added item is removed first. Using a singly linked list, we perform push() and pop() operations at the head for efficiency.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class Stack {
    Node* top;
public:
    Stack() { top = nullptr; }

    void push(int val) {
        Node* temp = new Node();
        temp->data = val;
        temp->next = top;
        top = temp;
    }

    void pop() {
        if (!top) {
            cout << "Stack Underflow\n";
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    void display() {
        Node* curr = top;
        while (curr) {
            cout << curr->data << " ";
            curr = curr->next;
        }
        cout << endl;
    }
};

int main() {
    Stack s;
    s.push(100);
    s.push(200);
    s.push(300);
    s.display();
    s.pop();
    s.display();
    return 0;
}
    

📝 Stack Output

300 200 100
200 100

🔁 Queue Using Linked List (FIFO)

In Queue, the first inserted element is removed first. We use a front and rear pointer to manage operations efficiently.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class Queue {
    Node* front;
    Node* rear;
public:
    Queue() {
        front = rear = nullptr;
    }

    void enqueue(int val) {
        Node* temp = new Node();
        temp->data = val;
        temp->next = nullptr;
        if (!rear) {
            front = rear = temp;
        } else {
            rear->next = temp;
            rear = temp;
        }
    }

    void dequeue() {
        if (!front) {
            cout << "Queue Underflow\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        if (!front)
            rear = nullptr;
        delete temp;
    }

    void display() {
        Node* curr = front;
        while (curr) {
            cout << curr->data << " ";
            curr = curr->next;
        }
        cout << endl;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}
    

📝 Queue Output

10 20 30
20 30

💡 Summary

• Linked Lists allow dynamic memory allocation—no fixed size needed.
• Stack uses head pointer only for fast push() and pop().
• Queue uses front and rear pointers to manage enqueue() and dequeue().