Stack and Queues

What is Stack?

The basis of stack is first in last out(FILO) Or last in first out (LIFO). To understand stack, consider example of plats. We place plats one over another. Let say we have 5 plats, named as p1, p2, p3, p4, and p5. Assume they are arranged in such a way that p2 is placed on p1, p3 is placed on p2, p4 on p3, and p5 on p4. As shown in the diagram.

 

Now you are clear with, what is stack. Now we will see where it is used and how we implement stack in c plus plus programming language.

Why Stack?

We see the functionality of forward and backward operations in our browsers. Similarly, we see functionalities like undo, redo in our text editor or any application like photo editors. The functionality of undo, redo is very common. It is used in many applications like in word, excel, photoshop, browsers, paint, and many other applications. Now if we think about what will be the best way to implement undo, redo functionality in our application, we will see the best data structure for this functionality will be stack data structure. We can do this task in easy way by using stacks. Now it is up to us how we use stack for this functionality. We can either use two stack for this, one to store information about forward operation and the other stack to store information about backward operation, Or we can just use one stack and carefully use it for this functionality.

In case of text editor, we can implement the functionality of undo, redo by using stack. We can pushing information about change in the file in stack, like if user typed any new word in the text file we can push it in the stack, now if the user undo changes we can remove the word from the text file and the words will be kept in stack, now if user wants to redo changes, we can just pop the words from our stack and show the desired result.

Mostly text editor clear the stack when the user start typing new text after undoing some changes and the text editor stores that new text in the stack. In case of simple notepad in our laptops, there is only one undo and redo possible, they might have implemented this without using stack. In case of visual studio, they have well maintained stack that stores changes of even single character in the code and have very well organized undo redo mechanism. These are all implemented through stacks depending on using stack in different ways.

How to implement Stack?

The implementation of stack is quite simple. It seems like stack is something new and different, but when it comes to implementation it is just a modified form of Linked List. We just need to store the pointer of head of the Linked List. In addition we need two functions push and pop in the List class. Push function, will add new node in the List and point head to this node. Pop function will return data of the last node and delete the last node and point the head Node to the second last node of the List. Such a List will be called as Stack data structure.

Code:

Node Class:

#pragma once

template<class T>

class node

{

public:

T data;

node<T>* next;

node(const T& d,node<T>* p=0)

{

data=d;

    next=p;

}

};

Stack code:

#pragma once

#include"node.h"

template <class T>

class stack

{

node<T>* top;

public:

stack()

{

top=nullptr;

}

               

bool IsEmpty();

bool push(const T & val);

bool pop(T & val);            

T Top();                   

void print();        

~stack()

{

while (!IsEmpty())

{

node<T>* temp = top->next;

delete top;

top = temp;

}

}

};

template<class T>

bool stack<T>::IsEmpty()

{

  return top==nullptr;

}

template<class T>

bool stack<T>::push(const T & val)

{

node<T>*temp=new node<T>(val, top);

top=temp;

    return true;

}

template<class T>

bool stack<T>::pop(T & val)

{

if(!IsEmpty())

{

val=top->data;

node<T>*temp=top->next;

delete top;

top=temp;

return true;

}

return false;

}

template<class T>

T stack<T>::Top()

{

if(!IsEmpty())

{

return top->data;

}

else

{

   T empty;

   return empty;

}

}

template<class T>

void stack<T>::print()

{

if (top == nullptr)

{

cout << "Stack is Empty." ;

}

else

{

node<T>* temp = top;

while (temp != nullptr)

{

cout << temp->data << "  ";

temp = temp->next;

}

}

cout<<endl;

}