Table of Contents

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.