Stack Implemented with Arrays and Templates in C++

What is a stack?

A stack is a data structure that stores a collection of elements and has at least two operations associated with it:

push 2. pop

Push and pop operation on a stack is done according to LIFO that is Last in, First Out order.

Push means to insert a new item at the end.
Pop means to remove an item from the end.

Implementation

We will implement our stack with a dynamically allocated array, you can also implement a stack with a linked list or dynamic arrays.

Stack class

The stack is a template class that has two data members:

stack: this is a dynamically allocated array.
top: this is the index of topmost element in our array.

Additionally, our class will have two template parameters:

type: type of the elements to be stored in the array.
size: maximum size of the stack

The stack will have the following member functions:

is_empty: Return true if the stack is empty, false otherwise.
push: insert 'element' at the top of the stack, if not overflow
pop: remove the element at the top of the stack if not underflow
display: print all elements in the stack to the console
get_top_element: returns the top element
clear: remove all elements in the stack and reset the top.

template <typename type, int size>
class Stack
{
    private:
        type* stack; 
        int top;   

    public:
        Stack();
        ~Stack();

        bool is_empty();    
        void push(type element);
        type pop();   
        void display();   
        type get_top_element(); 
        void clear();  
};

Stack Member Functions Implementation

Now let's define each function one by one.

Stack(): This is our constructor.

It creates a stack with an array of size 'size'.
It sets top to -1 to indicate that the stack is empty right now.

   template <typename type, int size>
   Stack<type, size> :: Stack()
   {
       stack = new type[size];
       top = -1;
   }

~Stack(): This is our destructor.

It will free the memory occupied by the dynamically allocated array of Stack.

Why? It's important to do this in destructor because when an object goes out of scope, the dynamically allocated array won't be released automatically.

Just remember that whatever you allocate dynamically in constructor must be freed in the destructor.

   template <typename type, int size>
   Stack<type, size> :: ~Stack()
   {
       delete[] stack;
   }

is_empty(): Return true if stack is empty, false otherwise.

How to check if the stack is empty?

If you think of this:

 if (top == -1)
     return true
 else
     return false

then it is correct but just unnecessary, because you can do it like this:

 template<typename type, int size>
 bool Stack<type, size> :: is_empty()
 {
     return top == -1;   
 }

because the Boolean operator == will itself return either true or false.

push(): insert 'element' at the top of the stack, if not overflow.

First, we need to check for overflow that is if we have more space in the stack or not for our new element, then if we do we save it otherwise we have two options -
- We can handle overflow with an if statement.
- We can handle overflow with exception handling. We will use this method because It's easier to ask forgiveness than it is to get permission.
- Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.

   template<typename type, int size>
   void Stack<type, size> :: push(type element)
   {
       if (top == size - 1)
       {
           throw out_of_range("Stack Overflow!! No more space to add elements.");
       }

       // insert element on next position in array
       stack[++top] = element; 
   }

pop(): Remove element at the top of stack if not underflow.

Just like we did with push() we will handle underflow that is no more elements to remove with exception handling.
Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.

   template<typename type, int size>
   type Stack<type, size> :: pop()
   {
       // check for underflow
       if (is_empty())
       {
           throw out_of_range("Stack Underflow!! No more element to pop.");
       }

       // pop element
       type element_popped = stack[top--];
       return element_popped;
   }

display(): print all elements in stack to console.

We will print elements in the LIFO order.

   template<typename type, int size>
   void Stack<type, size> :: display()
   {
       // check for empty stack
       if (is_empty())
       {
           cout << "Woops! stack is empty." << endl;
           return;
       }

       // loop over stack and display all elements
       for (int i = top; i >= 0; i--)
       {
           cout << stack[i] << " ";
       }
       cout << endl;
   }

get_top_element(): Returns the top element if stack is not empty.

Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.

   template <typename type, int size>
   type Stack<type, size> :: get_top_element()
   {
       if (is_empty())
       {
           throw out_of_range("Stack is empty!!");
       }
       return stack[top];
   }

clear(): Remove all elements in the stack and reset the top to -1.

   template <typename type, int size>
   void Stack<type, size> :: clear()
   {
       // free current memory occupied by the stack
       delete[] stack;
       // reset top
       top = -1;
       // assign new memory
       stack = new type[size];
   }

main Function to test our code:

We created a menu-driven main function to perform each operation on our stack.

Note

Remember to create a stack object with template syntax providing both parameters - type and size.
Remember to handle the possible exceptions thrown by push, pop, and get_top_element with a try-catch block.
The what function used while handling exceptions is a predefined function in all exception classes that will return the message we send while throwing the exceptions.

int main()
{
    cout << "Stack implemented as Array";

    const int stack_size = 5;
    Stack<int, stack_size> my_stack;

    int choice;
    while(true)
    {
        cout << "\nChoose an operation:\n";
        cout << "1. Push\n" << "2. Pop\n" << "3. Display\n"
        << "4. Display top\n" << "5. Stack empty?\n" << "6. Clear stack\n" 
        << "7. Exit" << endl;
        cout << "Enter a choice(1-6): ";
        cin >> choice;

        switch(choice)
        {
            case 1:
                int element;
                cout << "Enter element to push: ";
                cin >> element;
                try
                {
                    my_stack.push(element);
                    cout << "Pushed to stack\n";
                }
                catch(const std::exception& e)
                {
                    std::cerr << e.what() << '\n';
                }
            break;
            case 2:
                try
                {
                    int popped_element = my_stack.pop();
                    cout << "Top most element popped: " << popped_element << endl;                }
                catch(const std::exception& e)
                {
                    std::cerr << e.what() << '\n';
                }
            break;
            case 3:
                cout << "Stack right now:\n";
                my_stack.display();
            break;
            case 4:
                try
                {
                    cout << "Top most element: " << my_stack.get_top_element() << endl;
                }
                catch(const std::exception& e)
                {
                    std::cerr << e.what() << '\n';
                }
            break;
            case 5:
                my_stack.is_empty() ? cout << "Stack is empty right now.\n" : cout << "Stack is not empty right now.\n";
            break;
            case 6:
                my_stack.clear();
                cout << "Stack cleared.\n";
            break;
            case 7:
                exit(0);
            break;
            default:
                cout << "Invalid Input!! Please Try Again.\n" << endl; 
            break;
        }
    }

    return 0;
}

Blog

Stack Implemented with Arrays and Templates in C++

Yuvraj Singh Jadon

What is a stack?

Implementation

Stack class

Stack Member Functions Implementation

main Function to test our code:

Read more on Scaler Topics

Thanks.

Join Our Newsletter. No Spam, Only the good stuff.

Related