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.
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.
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.
