How To Implement a Stack Using a Linked List in C++

 

 

A stack is a data structure that follows the LIFO (last-in, first-out) principle. This means that the last element added to the stack is the first one to be removed. A linked list is a data structure consisting of nodes, each containing data and a reference (a pointer in C++) to the next node in the list.

 

To implement a stack using a linked list, we can create a Node class to represent each element in the list. Each Node object would contain two fields: data to store the actual data, and next to store a reference to the next node in the list.

 

• We begin by creating a Node class with two fields: data to store the actual data, and next to store a pointer to the next node in the list.

 

• We also define a constructor for the Node class that takes a data element as input and initializes the data field to the input value and the next field to nullptr.

   

    #include <iostream>

    using namespace std;

    class Node {
    public:
        int data;
        Node* next;

        Node(int data) {
        this->data = data;
        this->next = nullptr;
        }
    };

 

 

• We then create a Stack class to manage the linked list. The Stack class has a single field top, which is a pointer to the top node in the list.

 

• We define a constructor for the Stack class that initializes top to nullptr.

 

• We then define a push() method that takes a data element as input, creates a new Node object with that data, and inserts the new node at the top of the list. If top is nullptr, then we simply set top to the new node. Otherwise, we set the next field of the new node to the current top node, and then set top to the new node.

 

• We define a pop() method that removes the top node from the list and returns its data. If top is nullptr, then the stack is empty, so we simply return -1. Otherwise, we set top to the next node in the list, and then delete the old top node. We also return the data stored in the old top node.

 

• Finally, we define an is_empty() method that checks if top is equal to nullptr. If top is nullptr, then the stack is empty, so we return true. Otherwise, we return false.

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

        void push(int data) {
            Node* new_node = new Node(data);
            if (top == nullptr) {
                top = new_node;
            }
            else {
                new_node->next = top;
                top = new_node;
            }
        }

        int pop() {
            if (top == nullptr) {
                return -1;
            }
            else {
                int popped_data = top->data;
                Node* temp = top;
                top = top->next;
                temp->next = nullptr;
                delete temp;
                return popped_data;
            }
        }

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

 

 

Here's an example usage of the Stack class:

 

    int main() {
        Stack s;
        s.push(1);
        s.push(2);
        s.push(3);
        cout << s.pop() << endl;
        cout << s.pop() << endl;
        cout << s.pop() << endl;
        cout << s.pop() << endl; // this will print -1, indicating the stack is empty
        return 0;
    }

 

• In this example, we create a new Stack object s.

• We then push the elements 1, 2, and 3 onto the stack using the push() method.

• We then use the pop() method to remove and print the elements from the stack in LIFO order.

• Finally, we use the pop() method to attempt

 

Overall, implementing a stack using a linked list is relatively straightforward. The key idea is to use the next field of each node to keep track of the next node in the list. This allows us to easily insert and remove nodes from the list, and to keep track of the top node in the stack.