Stack (Linked List Implementation), Code ↔ Language

#dsa #datastructures

Creation of Stack (Linked List Implementation)

class Stack {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };

    Node* top;

public:
    // Constructor to initialize stack
    Stack() {
        top = nullptr;
    }
};

First, we will create a class named Stack.
It will contain a struct Node with the following properties:
- int data: Stores the value of the node.
- Node* next: Points to the next node in the stack.
- Node(int val): Constructor to initialize data with val and next with nullptr.
It will contain a property top:
- Node* top: Points to the top node of the stack.
We will declare a constructor Stack():
- It will initialize the top pointer to nullptr, indicating an empty stack.

Push Operation

void push(int item) {
    Node* newNode = new Node(item);
    newNode->next = top;
    top = newNode;
}

We will define a method push(int item):

It will take an integer item as input, which is the value to be pushed onto the stack.
We will create a new Node with item as its value.
We will set the next pointer of the new node to the current top node.
We will update top to point to the new node.

Pop Operation

int pop() {
    if (isEmpty()) {
        cout << "Underflow: Stack is empty.\n";
        return -1;
    }
    Node* temp = top;
    int poppedValue = temp->data;
    top = top->next;
    delete temp;
    return poppedValue;
}

We will define a method pop():

It will return an integer, which is the value removed from the top of the stack.
We will check if the stack is empty (using isEmpty()); if so, it will print "Underflow: Stack is empty." and return -1.
Otherwise, we will:
- Store the top node in a temporary pointer temp.
- Retrieve the value from temp and store it in poppedValue.
- Update top to point to the next node in the stack.
- Delete the temp node to free up memory.
- Return the poppedValue.

Peek Operation

int peek() {
    if (isEmpty()) {
        cout << "Stack is empty.\n";
        return -1;
    }
    return top->data;
}

We will define a method peek():

It will return an integer, which is the value at the top of the stack.
We will check if the stack is empty (using isEmpty()); if so, it will print "Stack is empty." and return -1.
Otherwise, it will return the value of the top node.

isEmpty Operation

bool isEmpty() {
    return top == nullptr;
}

We will define a method isEmpty():

It will return a boolean value indicating whether the stack is empty.
It will return true if top is nullptr, indicating that the stack is empty.
Otherwise, it will return false.

Full Code Implementation

#include <iostream>
using namespace std;

class Stack {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };

    Node* top;

public:
    // Constructor to initialize stack
    Stack() {
        top = nullptr;
    }

    // Destructor to free allocated memory
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // Push operation
    void push(int item) {
        Node* newNode = new Node(item);
        newNode->next = top;
        top = newNode;
    }

    // Pop operation
    int pop() {
        if (isEmpty()) {
            cout << "Underflow: Stack is empty.\n";
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    // Peek operation
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty.\n";
            return -1;
        }
        return top->data;
    }

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