Stack in C++ using linked list

Stack in C++ is a fundamental data structure that plays a crucial role in various aspects of programming and software development. This linear data structure follows a particular order in which operations are performed.

It follows the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It operates like a stack of plates, where you can only add or remove plates from the top.

NOTE

Download the Zip File by clicking on download button:

You can also get its code from GitHub Repository:

Implementing Stack in C++

Implementing a stack in C++ can be achieved using arrays or linked lists. But here we will discuss the operations of stack using linked list. Each method offers distinct advantages and challenges, from the simplicity and fixed size of array-based stacks to the dynamic nature and flexibility of linked list implementations.

Applications of Stack in C++

• Undo Mechanism in Text Editors
  • Many text editors use a stack to implement the undo mechanism. Each editing action (typing, deleting, etc.) is recorded as a command and pushed onto a stack. When the user wants to undo an action, the editor pops the most recent command from the stack and reverses its effect.
• Web Browser History
  • Web browsers maintain a history of visited web pages, which can be navigated using the back and forward buttons. This navigation history can be implemented using two stacks: one for storing the URLs of previously visited pages (back stack) and another for storing URLs of pages revisited after using the back button (forward stack).
• Backtracking Algorithms
  • Backtracking algorithms, such as depth-first search (DFS) in graph traversal and certain problem-solving techniques like the N-Queens problem, often use stacks to keep track of the current path or state. When exploring a solution space, the algorithm pushes choices onto the stack and pops them off when backtracking.

Code Breakdown

Node Structure

The Node structure represents each element in the stack. It contains an int data to store the element’s value and Node* next pointer to point to the next element in the stack.

struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
};

Stack Class

The Stack class encapsulates the stack operations and properties. It uses a private Node* top pointer to keep track of the top element in the stack.

Constructor and Destructor

• The constructor Stack() initializes the stack with top as nullptr, indicating an empty stack.
• The destructor ~Stack() deallocates all the nodes in the stack to prevent memory leaks.

Stack in C++ and its operations

• push(int data): Creates a new node with the provided data and adds it to the top of the stack.
• pop(): Removes the top element from the stack. It prints a message if the stack is empty (underflow condition).
• topElement(): Returns the data of the top element without removing it. If the stack is empty, it prints a message and returns -1.
• isEmpty(): Returns true if the stack is empty; otherwise, it returns false.

    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = top; // Point the new node to the current top
        top = newNode; // Update the top to be the new node
    }

    // Method to remove the top element from the stack
    void pop() {
        if (isEmpty()) {
            cout << "Stack Underflow. No element to pop." << endl;
            return;
        }
        Node* temp = top; // Store the current top
        top = top->next; // Update the top to the next element
        delete temp; // Delete the old top
    }

    // Method to get the top element of the stack
    int topElement() {
        if (!isEmpty()) {
            return top->data;
        }
        cout << "Stack is empty." << endl;
        return -1; // Return an error value or handle differently
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }

Main Function

Demonstrates the usage of the stack by pushing and popping elements. It also checks the top element at various stages to show how the stack changes after each operation.

Conclusion of what is stack in C++?

Stacks in C++ are a powerful and essential data structure, offering a unique combination of simplicity, efficiency, and flexibility. As programming and software development continue to evolve, the stack remains a critical tool for managing data and processes in a controlled, LIFO manner. Understanding and utilizing stacks effectively can significantly enhance the functionality and performance of C++ applications.

Source Code

Source Code of Stack and also implementation of stack in C ++ and its operations is given as:

#include <iostream>
using namespace std;

// Node structure for a single stack element
struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
};

// Stack class using a linked list
class Stack {
private:
    Node* top; // Pointer to the top element of the stack

public:
    // Constructor initializes the stack to be empty
    Stack() : top(nullptr) {}

    // Destructor to free the allocated memory
    ~Stack() {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }

    // Method to add an element to the stack
    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = top; // Point the new node to the current top
        top = newNode; // Update the top to be the new node
    }

    // Method to remove the top element from the stack
    void pop() {
        if (isEmpty()) {
            cout << "Stack Underflow. No element to pop." << endl;
            return;
        }
        Node* temp = top; // Store the current top
        top = top->next; // Update the top to the next element
        delete temp; // Delete the old top
    }

    // Method to get the top element of the stack
    int topElement() {
        if (!isEmpty()) {
            return top->data;
        }
        cout << "Stack is empty." << endl;
        return -1; // Return an error value or handle differently
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }
};

// Main function to demonstrate stack operations
int main() {
    Stack stack;

    // Demonstrate pushing elements
    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << "Top element after pushes: " << stack.topElement() << endl;

    // Demonstrate popping elements
    stack.pop();
    cout << "Top element after one pop: " << stack.topElement() << endl;
    stack.pop();
    cout << "Top element after two pops: " << stack.topElement() << endl;

    // Check for stack underflow
    stack.pop();
    cout << "Attempting one more pop..." << endl;
    stack.pop(); // This should trigger underflow condition

    return 0;
}