Implementation of Stacks Using Linked List in C++ and C

Implementation of Stacks Using Linked List in C++ and C

RAKSHIT SACHDEV  

As we have discussed about Static Stacks in one of our previous article where we also talked about the definition of stacks ie Stacks are kind of non primitive data structure where NON Primitive means derived from basic data types.

In the article we will be studying about Dynamic Stacks. Now when the word Dynamic comes it means we will be talking about implementation of stacks using Linked List.

For a better understanding of our video on Dynamic Stacks you should know about the traversal of linked list which is available here.

Before Starting  I would like to make a few points clear. Which are :

1. What is a Linked List?
2. Difference between Linked List and Array.
3. Differences between Static Stacks and Dynamic Stacks. 

1. Linked List :

A linked list is a set data collection (each called a NODE) each containing the address of its successor or predecessor or both depending on the type of the linked list.

In the above picture we see a Singular linear linked list where each node contains the address of the successive node.

For More information about Basic concept anf Traversal of Linked List click here.

2. We will be going through the major difference only in this article which is that in case of an array we have random access memory moreover the size of the array has to be mentioned before which makes it static and also the wastage of memory is also a disadvantage of arrays. On the contrary in case of linked list the memory allocation is Dynamic and so we don't have to mention the size and also no wastage of memory. This concept would be more clear in our article of linked list.

3. Difference between Static Stacks and Dynamic Stacks.
In case of Static Stacks we have to mention the size first and so it makes it a constraint the no of elements is fixed.
Whereas in case of dynamic stacks the constraint of size is not a problem as the size is not fixed and so we can push(insert) as many elements into the stack as we want.

Now Coming to our topic

We have the source code in C++

// Dynamic Stacks

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>


struct node
 { int adno;
   char name[20];
   float mks;
   node *link;
   };
node *top;

void push()
 { node *ptr;
   ptr=new node;
   if(ptr==NULL)
    { cout<<"Overflow";
      exit(0);
      }
   cout<<"\nEnter ADNO ";cin>>ptr->adno;
   cout<<"\nEnter Name ";gets(ptr->name);
   cout<<"\nEnter Marks ";cin>>ptr->mks;
   ptr->link=NULL;
   if(top==NULL)
    top=ptr;
   else
    {ptr->link=top;
     top=ptr;}
     }


void pop()
 { if(top==NULL)
    {cout<<"Under Flow";
     exit(0);
      }
   node *ptr;
   ptr=top;
   top=top->link;
   ptr->link=NULL;
   cout<<"Deleted\n";
   cout<<"\nAdmission Number "<<ptr->adno;
   cout<<"\nNAme "<<ptr->name;
   cout<<"\nMarks "<<ptr->mks;
   delete ptr;
   }

void display()
 { if(top==NULL)
    {cout<<"No Elements to Display";
     getch();
     exit(0);
     }
    node *ptr;
    ptr=top;
    while(ptr!=NULL)
     {  cout<<"\nAdmission Number "<<ptr->adno;
cout<<"\nNAme "<<ptr->name;
cout<<"\nMarks "<<ptr->mks;
cout<<'\n';
ptr=ptr->link;
}
  }


void main()
 {
   char ch;
   do {clrscr();
       cout<<"\nPush an Element     1";
       cout<<"\nPop an Element      2";
       cout<<"\nDisplay Stack       3";
       cout<<"\nExit                4";
       int n;
       cin>>n;
       switch(n)
{ case 1:{ clrscr();
  push();}break;

 case 2:{ clrscr();
  pop();}break;
 case 3:{ clrscr();
  display();}break;
 case 4:exit(0);

 }cout<<"Want to Continue? ";cin>>ch;
   }while(ch=='Y' || ch=='y');
  getch();
  }

,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

Source Code in C

#include<conio.h>
#include<stdio.h>
#include<process.h>

struct node
 { int adno;
   struct node *link;
   };
#define NODE struct node

NODE *top;

void push()
 { NODE *ptr=(NODE*)malloc(sizeof(NODE));
   if(ptr==NULL)
    { printf("Overflow");
      getch();
      exit(0);
      }
   printf("\nEnter ADNO ");
    scanf("%d",&ptr->adno);
   ptr->link=NULL;
   if(top==NULL)
    top=ptr;
   else
    {ptr->link=top;
     top=ptr;}
     }


void pop()
 { NODE *ptr=(NODE*)malloc(sizeof(NODE));

  if(top==NULL)
    { printf("Under Flow");
     exit(0);
      }

    ptr=top;
    top=top->link;
    ptr->link=NULL;
   printf("\nDeleted\n");
   printf("\nAdmission Number %d ",ptr->adno);
   free(ptr);
   }

void display()
 { NODE *ptr=(NODE*)malloc(sizeof(NODE));
   if(top==NULL)
    { printf("\nNo Elements to Display");
      getch();
      exit(0);
    }
    ptr=top;
    while(ptr!=NULL)
     {  printf("\nAdmission Number %d",ptr->adno);

ptr=ptr->link;
     }
  }


void main()
 {
   int ch,n;
   do {clrscr();
       printf("\nPush an Element     1");
       printf("\nPop an Element      2");
       printf("\nDisplay Stack       3");
       printf("\nExit                4\n");
       scanf("%d",&n);
       switch(n)
 { case 1:{ clrscr();
   push();
 }break;

   case 2:{ clrscr();
   pop();
 }break;
   case 3:{ clrscr();
   display();
 }break;
   case 4:exit(0);

   }printf("\nWant to Continue?(yes=1) ");
     scanf("%d",&ch);
   }while(ch==1);
  getch();
  }

Program on Static Stacks in C/C++

Program on Static Stacks in C/C++

RAKSHIT SACHDEV  

Stacks

Stacks are a type of Non Primitive Data Structures in C/C++ where NON Primitive means derived from basic data types ie. int, char, float. 

It is an ordered collection of elements that works on the principle of LIFO which is an abbreviation for LAST IN FIRST OUT.  

In layman's language this means the element that was input at the last is to be popped out first.

Now when I say element popped it means only one element can be deleted each time also the position is fixed ie the last position. 

Summing it up by saying both the operations can be done from only one end.

  

So if I talk about Static Stacks the word static here means the size will be fixed hence it follows the concept of arrays. And so I started the index as 0. 

Relating the above diagram with a real life example. If you have a stack of CD's which CD can you pull out first? The CD at the Top? Which is the last CD you had put in the stack. And So goes here. The first element that can be popped out is 'C at index 2.

Now there are two Operations on Stacks

1. Push which means insertion.

2. Pop which means deletion.

                             

Now Here is the Syntax : 

C++

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<process.h>

const int size=20;

int top=-1, a[size];

void push()

 { if(top==size-1)

    { cout<<"Overflow";

      exit(0);

      }

   top++;

   int num; cin>>num;

   a[top]=num;

    }

void pop()

 { if(top==-1)

    { cout<<"Underflow";

      exit(0);

      }

   int num;

   num=a[top];

   cout<<"Deleted "<<num;

   top--;

   }

void display()

 { for(int i=0;i<=top;i++)

    {cout<<a[i];

     cout<<'\n';

     }

  }

void main()

 { char ch;

   do {clrscr();

       cout<<"\nPush an Element     1";

       cout<<"\nPop an Element       2";

       cout<<"\nDisplay Stack           3";

       cout<<"\nExit                          4 ";

       int n;

       cin>>n;

       switch(n)

{ case 1:{ clrscr();

   push();}break;

  case 2:{ clrscr();

   pop();}break;

  case 3:{ clrscr();

   display();}break;

  case 4:exit(0);

  }cout<<"Want to Continue? ";cin>>ch;

   }while(ch=='Y' || ch=='y');

  getch();

  }

---------------------------------------------------

C

#include<conio.h>

#include<stdio.h>

#include<process.h>

int top=-1, a[10];

void push()

 { int num;

   if(top == 10)

    { printf("\nOverflow");

      getch();

      exit(0);

    }

   top++;

    scanf("%d",&num);

   a[top]=num;

    }

void pop()

 { int num;

   if(top==-1)

    { printf("\nUnderflow");

      getch();

      exit(0);

    }

   num = a[top];

   printf("Deleted %d",num);

   top--;

 }

void display()

 { int i;

   for( i = top; i>=0; i--)

    printf("%d\n",a[i]);

  }

void main()

 { char ch;int n;

   do {clrscr();

       printf("\nPush an Element     1");

       printf("\nPop an Element      2");

       printf("\nDisplay Stack       3");

       printf("\nExit                4");

       scanf("%d",&n);

       switch(n)

{ case 1:{ clrscr();

   push();}break;

  case 2:{ clrscr();

   pop();}break;

  case 3:{ clrscr();

   display();}break;

  case 4:exit(0);

  }printf("\nWant to Continue? ");scanf("%d",&ch);

   }while(ch=='Y' || ch=='y');

  getch();

  }

Download Turbo C++ on Windows(Any Version)

Download Turbo C++ on Windows(Any Version)

RAKSHIT SACHDEV  

Turbo C++ is a discontinued C++ compiler and integrated development environment and computer language originally from Borland. Most recently it was distributed by Embarcadero Technologies, which acquired all of Borland's compiler tools with the purchase of its CodeGear division in 2008. The original Turbo C++ product line was put on hold after 1994 and was revived in 2006 as an introductory-level IDE, essentially a stripped-down version of their flagship C++Builder. Turbo C++ 2006 was released on September 5, 2006 and was available in 'Explorer' and 'Professional' editions. The Explorer edition was free to download and distribute while the Professional edition was a commercial product. In October 2009 Embarcadero Technologies discontinued support of its 2006 C++ editions. As such, the Explorer edition is no longer available for download and the Professional edition is no longer available for purchase from Embarcadero Technologies. Turbo C++ is succeeded by C++Builder.

source: https://en.wikipedia.org/wiki/Turbo_C%2B%2B

So we'll be using an emulator called DosBox tu run Turbo C++ in any version of Windows.

Step 1.

Click here To Download the Setup.

Step 2.

Click the Download tab

Step 3.

After the Download is complete click on the setup to install. it will pop to this screen. Click Next and then install.

Step 4.

After the installation is complete you'll have your Turbo C++ installed in your C drive.

 C > TurboC++ .