Stacks (LIFO) using Linked List (Self-referential Structure)
In Board Exams for CBSE Class XII Computer Science using C++ they might ask a question to implement stacks using Linked Lists or Arrays. This tutorial describes how to implement Stacks using linked list. It uses the concept of LIFO (Last in First Out).
How to implement Stacks (LIFO) using Linked Lists?
What are linked lists?
- When we are using arrays, we are requesting a contiguous memory block. This is same as if group of people want to travel by the train on the same coach. This is fine till the time group is small. It might not be easy for a large group. Same holds true for memory – Array becomes less suitable when you want to store very large amount of data.
- Array size need to be known while writing a program. Arrays employ static binding. Which means arrays can’t grow or shrink in size at the run time.
- Linked Lists on the other hand can be used to overcome the limitations of the arrays, discussed above.
- Linked Lists are implemented using self-referential structure.
- Both Arrays and Linked Lists are linear by structure, Arrays use contiguous memory location and individual elements are accessed using the position (known as index) of the element.
- Linked Lists on the other hand used dynamic memory and jumps to the next element (also known as node) using the address of the next node stored within the node.
- Node element is created with the help of self-referential structure.
Explanation – Post-mortem of the code
Lets understand and identify self-referential structure in our program:
struct data
{
int val1, val2;
data *next;
};
The above structure can be seen as made up of two parts:
- Data, and a
- Link to the next location
In our case val1 and val2 are data members, while a pointer *next will be used to store the address of the next node.
- Make a note – inside function main() a pointer to the structure ‘data‘ defined above has been declared by the name top.
void main()
{
data *top=NULL; // A pointer to structure
Let us understand the function push()
data* push(int v1, int v2, data *TOP)
- Here data* is a return type (As function is going to return updated *TOP)
- push is the function name
- int v1, int v2 are first two arguments to receive values (v1 and v2) from main function()
- data *TOP is the third argument to receive the current address of pointer *top from main function()
- Inside function we create another pointer data *tmp and allocate memory using new operator.
{
data *tmp=new data(); //Allocating memory
if(!tmp) //checking memory is allocated successfully or not
{
return NULL;
}
- Next we assign values v1 and v2 to newly allocated memory block – *tmp
- Since we don’t know if there will be another node or not, we initially assign NULL to tmp->next.
tmp->val1=v1; tmp->val2=v2; tmp->next=NULL;
- In the next statement, we check if TOP is NULL or not. (If TOP is NULL, it indicates stack is empty and we are about to add a new node).
- If TOP is not NULL, then this new node should become the top node (by inserting new node before the top most node) as shown below
if(TOP==NULL)
{
TOP=tmp; // If we are adding the first node, TOP points to that
}
else
{
tmp->next=TOP; // If we are adding node at the end of list, new node should first point to TOP, and
TOP=tmp; // then TOP should point to new node, so that new node becomes the top most node
}
Let us understand the function pop()
data* pop(data *TOP)
- Here data* is a return type (As function is going to return updated *TOP)
- pop() is the function name
- data *TOP is the argument to receive the current address of pointer *top from main function()
- Next, we check if there is any record to pop (delete).
if(TOP==NULL) //Checking id stack is empty
{
cout<<"\nStack Empty";
getch();
return NULL; //Null is returned to indicate nothing to pop (delete)
}
- If TOP is NULL, that means stack is empty and hence nothing to pop.
- If stack is not empty, then TOP node is removed from the stack as shown below
else
{
data *tmp=TOP; // Saving the top most node(record) in tmp
TOP=TOP->next; // Now next node (record) should become the TOP node
tmp->next=NULL; // Isolating tmp from the stack
cout<<"\nPopped: "<<tmp->val1<<","<<tmp->val2; // Displaying details of the node that has been popped
getch();
return TOP; // Return the address of new TOP (newly found top
// record in the stack after emoving the top most node (record)
}
Let us understand the function disp()
- if TOP is not NULL (when stack is not empty!!!), the disp() function just loops through the entire stack from top most element to the last node (or rather a node that was pushed to the stack before any other existing node in the stack). This is because stack is based on the principal “LIFO” i.e Last In First Out.
Listing of the complete program
#include<iostream.h>
#include<conio.h>
struct data
{
int val1, val2;
data *next;
};
data* push(int v1, int v2, data *TOP)
{
data *tmp=new data();
if(!tmp)
{
return NULL;
}
else
{
tmp->val1=v1;
tmp->val2=v2;
tmp->next=NULL;
if(TOP==NULL)
{
TOP=tmp;
}
else
{
tmp->next=TOP;
TOP=tmp;
}
}
return TOP;
}
data* pop(data *TOP)
{
if(TOP==NULL)
{
cout<<"\nStack Empty";
getch();
return NULL;
}
else
{
data *tmp=TOP;
TOP=TOP->next;
tmp->next=NULL;
cout<<"\nPopped: "<<tmp->val1<<","<<tmp->val2;
getch();
return TOP;
}
}
int disp(data *TOP)
{
if(TOP==NULL)
{
return -1;
}
else
{
data *t=TOP;
while(t!=NULL)
{
cout<<"\n"<<t->val1<<","<<t->val2;
t=t->next;
}
getch();
}
}
void main()
{
data *top=NULL;
int choice=0;
while(choice!=4)
{
clrscr();
cout<<"\n 1. Push";
cout<<"\n 2. Pop";
cout<<"\n 3. Show";
cout<<"\n 4. Exit";
cout<<"\n Enter choice: ";
cin>>choice;
if(choice==1)
{
int v1,v2;
cout<<"\nEnter value1 and value2: ";
cin>>v1>>v2;
top=push(v1,v2,top);
}
else if(choice==2)
{
top=pop(top);
}
else if(choice==3)
{
int chk=disp(top);
if(chk==-1)
{
cout<<"\nStack Empty!!!";
}
}
}
}
Download the complete Program
Stacks using Linked Lists (Self -referential structure) 1.31 KB 110 downloads
A complete C++ program (as per CBSE CS Syllabus) to demonstrate the working of Stacks...Conclusion
As I always say this tutorial with complete program is provided to my students for only learning purpose. Student should practice on their own using this tutorial only for reference purpose.
Happy Coding.
Teaching, Coding and Sharing is his passion. A true mentor and motivator. C/C++, Python, Java, Web Technologies (html5 / CSS/ Javascript/ JQuery,Bootstrap, nodeJS ,PHP etc.) and a WordPress enthusiast with more than two decades of experience.
