Stack (Linked List Implementation), Code ↔ Language

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;
    }
};

1. First, we will create a class named Stack.

2. 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.

3. It will contain a property top:

   • Node* top: Points to the top node of the stack.

4. 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;
    }
};