C++ Stacks

Stack Introduction

This article explains about basics of the stack data structure and demonstrates implementation of stack using arrays and linked lists.

• Stack is a last-in, first-out (LIFO) data structure. i.e. the element added last to the stack will be the one to be removed first.
• Typical use cases of stacks include:- (1) During debugging it is quite common to examine the function call stack during panics. (2) In RTOS like Symbian there are concepts like cleanup stack to avoid memory leaks.
• Some of the common terminology associated with stacks include PUSH, POP and TOP of the stack.
• PUSH refers to adding an element to the stack.
• POP refers to removing an element from the stack.
• TOP refers to the first element that could be POPed (or) the last element PUSHed.
• Diagram below explains the stack.

Implementation of a simple stack using arrays

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

class StackOverFlowException 
{
    public:
        StackOverFlowException() 
        {
            cout << "Stack overflow" << endl;
        }
};

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

class ArrayStack 
{    
    private:        
        int data[MAX_SIZE];        
        int top;    
  public:        
      ArrayStack() 
      {            
          top = -1;        
    }        
    
    void Push(int element)
    {            
        if ( top >= MAX_SIZE ) 
            {            
                throw new StackOverFlowException();
            }                   
            data[++top] = element;        
    }        
            
    int Pop()
    {            
        if ( top == -1 ) 
            {            
                throw new StackUnderFlowException();            
            }            
            return data[top--];        
    }        
    
    int Top() 
    {            
        return data[top];        
    }
    
    int Size() 
    {
        return top + 1;
    }
    
    bool isEmpty() 
    {
        return ( top == -1 ) ? true : false;
    }
};

int main()
{    
    ArrayStack s; 
    try {
        if ( s.isEmpty() ) 
            {
            cout << "Stack is empty" << endl;    
            }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-

Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured

Implementation of a simple stack using linked lists

#include <iostream>
using namespace std;

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

struct Node 
{
    int data;
    Node* link;
};

class ListStack 
{
    private:                 
        Node* top;
        int count;
            
  public:        
      ListStack() 
      {            
          top = NULL;
          count = 0;        
    }        
    
    void Push(int element)
    { 
        Node* temp = new Node();
        temp->data = element;
        temp->link = top;
        top = temp;     
        count++;          
    }        
            
    int Pop()
    {            
        if ( top == NULL ) 
            {            
                throw new StackUnderFlowException();            
            }        
            int ret = top->data;    
            Node* temp = top->link;
            delete top;
            top = temp;
            count--;
            return ret;        
    }        
    
    int Top() 
    {            
        return top->data;        
    }
    
    int Size() 
    {
        return count;
    }
    
    bool isEmpty() 
    {
        return ( top == NULL ) ? true : false;
    }
};

int main()
{    
    ListStack s; 
    try {
        if ( s.isEmpty() ) 
        {
            cout << "Stack is empty" << endl;    
        }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-

Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured