Home C++ Stack in C++

Stack in C++

The true essence of learning a language is getting familiar with data structures in that language. Data Structure is a fundamental concept as programming is all about storing data, retrieving data, and dealing with data types. The most common data structure we come across is an array. An array is a basic abstract data type that linearly holds data.

The items of an array can be as simple as integers and as complex as user-defined objects. The previous article talks all about that in a basic array. Today, let’s discuss something different like stacks and queues.

Stack

A stack is an abstract data type that holds a sequence of elements like an array. Unlike arrays, stack uses LIFO i.e. last in first out structure. A good example of a stack data structure could be a stack of books or plates.

stack

The image above shows how plates are arranged in the stack, and the last plate added will be the first plate that will be picked up. The applications involving stack are countless, like when a function is called, the program’s return address is saved on the stack, and the local variables in a function are also stored in the stack.

Stack Operations

Let’s discuss stack from the perspective of code. When creating a stack, there are mainly two operations, namely, push and pop. The push function fills up the stack, and the pop function removes the last element. These operations are better demonstrated through the figure shown below.

push
pop

So first 5 was pushed into the stack and then 10. To retrieve the elements, we first pop 10 and then 5. Now let’s implement this through C++ code to have a better understanding of stack data structure.

Stack using Array

#include<iostream>
using namespace std;
//Exception class
class Arrayindexoutofbound:public std::runtime_error
{
	public:
		//default constructor of exception class with error message
    	Arrayindexoutofbound():std::runtime_error("Array index out of bound!")
    	{
		}
};
//template class
template<class T>
//stack created using an array
class ArrayStack
{
	private:
  	    //Pointer type variable that can be of any data type
		T* Array;
  	    //display the top element of the stack
		int top;
        //size of the stack
		int size;
	public:
  	    //parametrized constructor to set size of the stack
		ArrayStack(int s)
		{
			size=s;
            //1D Array of any data type having the size specified
			Array=new T[size];
            //initially the top of the stack is empty
			top=-1;
		}
  	    //See the top of the stack
        T& peek()
		{
          //if stack is empty then will throw an exception
			if(top==-1)
			throw(Arrayindexoutofbound());
			else
			return Array[top];
		}
        //returns true is the stack is empty and flase if the stack is not empty
		bool IsEmpty()
		{
			if(top==-1)
			return true;
			else
			return false;
		}
  	   //returns true if the stack is full
		bool IsFull()
		{
			if(top==size-1)
			return true;
			else return false;
		}
  	    //push function to push T type data to the stack and increment top so that it points to the next empty space
		void Push(T d)
		{
			if(!IsFull())
			{
              //Assign the value d to the top of the stack
				Array[top]=d;
				top++;
			}
		}
  	   // pop element is the stack is not empty
		T Pop()
		{
			T element;
			if(!IsEmpty())
			{
				top--;
				element=Array[top];
			}
			return element;
		}
	
};
int main()
{
  // creating a stack of type int, size = 5
	Stack <int> Data(5);
	Data.push(5);
	Data.push(4);
	Data.push(3);
	Data.push(2);
	Data.push(1);
	cout<<Data.pop()<<endl;
	cout<<Data.pop();
	
}

The above example is a static stack. A dynamic stack can also be built using linked lists instead of arrays. A dynamic stack starts with a linked-list and then expands further one node at a time as the value is pushed, and the dynamic stack is never full until the system runs out of memory.

Stack using List

In this tutorial, we have created a singly linked list of our own rather than using the C++ built-in library and created a stack from the linked list as shown below.

#include<iostream>
using namespace std;
// template node class to create a linked list
template<class T>
class Node
{
	private:
		T Data;
		Node<T> *Next;
	public:
		//default constructor
		Node():Data(0),Next(0)
		{
			
		}
		//parameterized constuctor
		Node(const T &d)
		{
			Data=d;
			Next=0;
		}
		Node(Node<T> *n)
		{
			Next=n;
		}
		void SetNode(Node<T> *n)
		{
			Next=n;
		}
		Node <T>* GetNode()
		{
			return Next;
		}
		void SetData(const T &d)
		{
			Data=d;
		}
		T GetData() const
		{
			return Data;
		}
		
};
// a function to display the length of list at some point in the program
template<class T>
int LengthOfList(Node<T>* n,int count)
{
   	if(n!=0)
   	{
   		n=n->GetNode();
   		count++;
   		LengthOfList(n,count);
   	}
   	else
   	return count;
   
}
// The singly linked list class that has a pointer of the node class
template<class T>
class SinglyLinkedList
{
	private:
		Node <T>* Head;
		//private function
  	    //helper function that is used to clear the linked list
		void DeleteAll()
		{
			Node<T>* current=Head;
			Node<T>* temp=current;
			while(current!=0)
			{
				current=current->GetNode();
			}
			temp->SetNode(0);
			delete temp;
			temp=current;
			Head=0;
		}
	public:
		
		//default constructor
		SinglyLinkedList()
		{
			Head=0;
		}
		Node<T>* GetHead()
		{
			return Head;
		}
		//copy constructor
		SinglyLinkedList(const SinglyLinkedList &rhs)
		{
			Head=0;
			Node<T>* current=rhs.Head;
			Node<T>* Last=0;
			//while loop
			while(current!=0)
			{
			    //Assigning the current value to a node
				Node<T>* newnode=new Node<T> (current->GetData());
				if(Head==0)
				{
					Head=newnode;
					Last=Head;
				}
				else
				{
				  Last->SetNode(newnode);
					Last=newnode;
				}
				current=current->GetNode();
			}
	    }
	    
	    //Assignment operator overload
	    SinglyLinkedList<T>& operator =(const SinglyLinkedList &rhs )
	    {
	    	if(this!=&rhs)
	    	{
	    		//private function
	    		DeleteAll();
	    		Head=0;
			Node<T>* current=rhs.Head;
			Node<T>* Last=0;
			//while loop
			while(current!=0)
			{
			    //Assigning the current value to a node
				Node<T>* newnode=new Node<T> (current->GetData());
				if(Head==0)
				{
					Head=newnode;
					Last=Head;
				}
				else
				{
					Last->SetNode(newnode);
					Last=newnode;
				}
				current=current->GetNode();
			}
	    		
			}
			return *this;
		}
		
		//Destructor
		~SinglyLinkedList()
		{
			DeleteAll();
		}
		void InsertAtFront(T d)
		{
			Node<T>* temp=new Node <T>(d);
			if(Head==0)
			{
				Head=temp;
			}
			else
			{
				temp->SetNode(Head);
				Head=temp;
			}
		}
		
		//element returned after removing
		T RemoveFromFront()
		{
			if(Head==0)
			{
				cout<<"List is Empty";
			}
			else
			{
				Node<T>* temp=Head;
				Head=Head->GetNode();
				temp->SetNode(0);
				//returning the element that is extracted from the list
				return (temp->GetData());
			}
		}


		void InsertAtLast(T d)
		{
			Node<T>* temp=new Node <T>(d);
			if(Head==0)
			{
				Head=temp;
			}
			else
			{
				Node<T>* current=Head;
				while(current->GetNode()!=0)
				{
					current=current->GetNode();
				}
				current->SetNode(temp);
			}
		}
		
		T RemoveFromLast()
		{
			Node<T>* temp;
			if(Head==0)
			{
				cout<<"list is empty";
			}
			else
			{
				Node<T>* current=Head;
				temp=Head;
				//traversing till the second last node
				while(current->GetNode()->GetNode()!=0)
				{
					current=current->GetNode();
				}
				temp=current->GetNode();
				current->SetNode(0);
				T element=temp->GetData();
				delete temp;
				return element;
			}
		}
		void DeleteithNode()
		{
			int pos;
			Node<T>* temp;
			Node<T>* current=Head;
			cout<<"Enter the position of node to delete:";
			cin>>pos;
			for(int i=2;i<pos;i++)
			{
				if(pos<=LengthOfList(Head,0))
				{
				current=current->GetNode();
				}
				
			}
			temp=current->GetNode();
			current->SetNode(temp->GetNode());
			delete temp;
		}
	
		
	void Print()
		 {
		 	if(Head==0)
		 	{
		 		cout<<"List is Empty!"<<endl;
		 	}
		 	else
		 	{
		 		Node<T>* temp=Head;
			 	while(temp!=0)
			 	{
			 		cout<<temp->GetData()<<endl;
			 		temp=temp->GetNode();
				}
				cout<<endl;
		 	}
		 } 
};
//template stack class made from singly linked list
template <class T>
class Stack
{
	private:
        //list type pointer in the stack class
		SinglyLinkedList <T>* stackdata;
		int top;
	public:
		Stack()
		{
			top=-1;
            //creating a list just like we previously created an array
			stackdata=new SinglyLinkedList <T>;
		}
		void Push(T d)
		{
			if(top==-1)
			{
              // inserting data from the end of the list
				stackdata->InsertAtLast(d);
			}
			else
			cout<<"Stack is Full";
		}
		T Pop()
		{
			 T element;
            //removing data from the end of the list
			 element=stackdata->RemoveFromLast();
			 return element;
		}
		T Peek()
		{
			return stackdata->Head->GetData();
		}
		void Display()
		{
			stackdata->Print();
		}
		void DeleteFromMiddle()
		{
			stackdata->DeleteithNode();
		}
		
	
};
//driver program
int main()
{ 
   Stack <int> data;
   data.Push(5);
   data.Push(6);
   data.Push(7);
   data.Display();
   cout<<data.Pop()<<endl;
   cout<<data.Pop()<<endl;
   data.Display();
   data.Display();
   
}

Why use templates for all these implementations? The special quality of these implementations is that they will work for any data type, not just numbers. They can work for floats and strings, and other complicated objects. An example could be a class called plates to create a stack of plate types bypassing stack <plate> data instead of int.

Conclusion

Stacks can also be constructed using built-in libraries of lists, but creating your own data structure library is an art. We have many more articles coming up that would create our own data structure library step by step, so stay tuned.

You may also like

Leave a Comment

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More