Linked List Implementation of Stack in C++

Write a class which will implement the Stack data structure in C++. Give the declaration & definition of the class. Also define the Node. For simplicity, you may assume stack to hold integer data type.

Solution:

There can be multiple type of implementations of Stack. Two most popular ones are

1. Array implementation:

• Stack is stored in an Array.
• Easy to implement.
• Is of fixed size (i.e if the array is of size 100, then it will occupy 100 memory locations even if there are, say 2 elements in the stack, also we cannot store more that 100 elements in the Stack).

2. Linked List Implementation:

• Stack is stored in a Linked List.
• Have to manipulate pointers.
• The size of this implementation is dynamic and it takes memory proportional to the actual number of elements in Stack.

 In both the implementations, the push and pop operations are constant-time operations, i.e O(1)

In this post we will only consider the Linked List implementation of Stack (you may try Array implementation on your own). For Linked list implementation, the stack is

A linked list where Insertion (Push) and Deletion (Pop) are performed from the same end (lets say at head of the list).

Lets first define the Node structure :

    struct Node{
        int data;
        Node* link;
        /* Constructors. Both the properties (data & link) are initialized
         * in the Member Initialization List itself. So the body of constructors is empty*/
        Node():data(0), link(NULL) {}
        Node(int n):data(n), link(NULL) {}
    };

Given this definition of Node of Linked List, The declaration of Stack class (may go in mystack.h , file) will be as below:

    class MyStack
    {
       private:
          // Will always point to the head of the list (First element)
          Node * top;
       public:
          // Default Constructor
          MyStack():top(NULL){}
          void push(int);
          int pop();
          // returns the top-most element.
          int getTop();
          // returns true if the Stack is Empty, else return false.
          int isEmpty();
    };

Definition of the functions of Stack class will be in the .cpp file (mystack.cpp)

    /** Function to push element in the Stack.
     *  Will Create a new Node and put it at the head of the linked list.
     */
    void MyStack::push(int d)
    {
        Node* temp = new Node(d);
        temp->link = top;
        top = temp;
    }
    /** Function to Pop element in the Stack.
     *  Will delete the node pointed to by top of the list and return its value.
     *  If Stack is NULL then returns -1
     */
    int MyStack::pop()
    {
        int retValue = -1;
        if(top != NULL){
           retValue = top->data;
           Node * temp = top;
           top = top->link;
           delete temp;
        }
        return retValue;
    }
    /** Returns the element at the Top of the Stack
     *  Top is the first element of the Stack.
     *  If Stack is NULL then returns -1
     */
    int MyStack::getTop()
    {
        if(top)
           return top->data;
        else
           return -1;
    }
    /** Check if the Stack is Empty or Not
     *  If top is NULL then the Stack is Empty.
     */
    int MyStack::isEmpty()
    {
        return ( (top == NULL)? true : false);
    }