C++ implementation of Stack using Linked list
INTRODUCTION
Stack is a data structure which follows LIFO i.e. Last-In-First-Out method.
The data/element which is stored last in the stack i.e. the element at top will be accessed first.
And both insertion & deletion takes place at the top.
When we implement stack using array :
- We create an array of predefined size & we cannot increase the size of the array if we have more elements to insert.
- If we create a very large array, we will be wasting a lot of memory space.
- So to solve this lets try to implement Stack using Linked list where we will dynamically increase the size of the stack as per the requirement.
#Implementation using Linked List
As we know that we use a head pointer to keep track of the starting of our linked list, So when we are implementing stack using linked list we can simply call the head pointer as top to make it more relatable to stack.
Push (insert element in stack)
- The push operation would be similar to inserting a node at starting of the linked list
- So initially when the Stack (Linked List) is empty, the
toppointer will beNULL. Let's suppose we have to insert the values 1, 2 & 3 in the stack. - So firstly we will create a new Node using the
newoperator and return its address in temporary pointerptr. - Then we will insert the value 1 in the data part of the Node :
ptr->data = valueand make link part of the node equal to top :ptr->link=top. - Finally we will make
top = ptrto point it to the newly created node which will now be the starting of the linked list and top of our stack.
- Similarly we can push the values 2 & 3 in the stack which will give us a linked list of three nodes with top pointer pointing to the node containing value 3.
Pop (delete element from stack)
- The pop operation would be similar to deleting a node from the starting of a linked list.
- So we will take a temporary pointer
ptrand equate it to thetoppointer. - Then we will move the top pointer to the next node i.e.
top = top->link - Finally, we will delete the node using
deleteoperator and pointerptri.edelete(ptr) - After we pop once our stack will look something like this:
isEmpty (check if stack is empty or not)
- To check if the stack is empty or not we can simply check if top==NULL, it means that the stack is empty
Program:
#include <iostream>
using namespace std;
//Structure of the Node
struct Node
{
int data;
Node *link;
};
// top pointer to keep track of the top of the stack
Node *top = NULL;
//Function to check if stack is empty or not
bool isempty()
{
if(top == NULL)
return true; else
return false;
}
//Function to insert an element in stack
void push (int value)
{
Node *ptr = new Node();
ptr->data = value;
ptr->link = top;
top = ptr;
}
//Function to delete an element from the stack
void pop ( )
{
if ( isempty() )
cout<<"Stack is Empty";
else
{
Node *ptr = top;
top = top -> link;
delete(ptr);
}
}
// Function to show the element at the top of the stack
void showTop()
{
if ( isempty() )
cout<<"Stack is Empty";
else
cout<<"Element at top is : "<< top->data;
}
// Function to Display the stack
void displayStack()
{
if ( isempty() )
cout<<"Stack is Empty";
else
{
Node *temp=top;
while(temp!=NULL)
{ cout<<temp->data<<" ";
temp=temp->link;
}
cout<<"\n";
}
}
// Main function
int main()
{
int choice, flag=1, value;
//Menu Driven Program using Switch
while( flag == 1)
{
cout<<"\n1.Push 2.Pop 3.showTop 4.displayStack 5.exit\n";
cin>>choice;
switch (choice)
{
case 1: cout<<"Enter Value:\n";
cin>>value;
push(value);
break;
case 2: pop();
break;
case 3: showTop();
break;
case 4: displayStack();
break;
case 5: flag = 0;
break;
}
}
return 0;
}
OUTPUT:
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
1
Enter Value:
33
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
1
Enter Value:
45
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
1
Enter Value:
66
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
1
Enter Value:
77
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
2
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
4
66 45 33
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
3
Element at top is : 66
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
5
Comments