Implementation of Stack Data Structures using Linked List with Program

Dynamic Implementation of Stack

Prev Next

---

The major problem with the stack implemented using array is, it works only for fixed number of data values. That means the amount of data must be specified at the beginning of the implementation itself.

A stack implemented using linked list works for variable size of data. So, there is no need to know the size at the beginning of the implementation.

In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its next node in the list. The next field of the first element must be always NULL.

Algorithm to push an element in a linked stack

Step 1: Create NEW_NODE using createnode()

NEW_NODE = createnode()

Step 2: IF there is no memory available (NEW_NODE == NULL)

Write "Stack Overflow"

Step 3: IF the stack is empthy (START == NULL)

START = NEW_NODE
TOP = NEW_NODE

Step 4: If the Stack is not empthy

PTR = START
while(PTR -> NEXT != NULL)
{

PTR = PTR -> NEXT

}
PTR -> NEXT = NEW_NODE
TOP = NEW_NODE

Step 5: Write "Data pushed sucessfully.... " and EXIT

Algorithm to pop an element in a linked stack

Step 1: IF the stack is empthy (TOP == NULL)

Write "Stack is Empty!! Deletion is not possible!!"

Step 2: IF stack has only one element (START -> NEXT == NULL)

START = NULL
free(TOP)
TOP = NULL

Step 3: IF stack has more than one element

PTR = START
while(PTR -> NEXT != TOP)
{

PTR = PTR -> NEXT

}
PTR -> NEXT = NULL
free(TOP)
TOP = PTR

Step 5: EXIT

C program to implement a linked stack.

       
#include<stdio.h>
#include<conio.h>
struct stack
{
  int data;
  struct stack *next;
};
typedef struct stack node;
node *start=NULL;
node *top = NULL;

node* getnode()
{
  node *newnode;
  newnode=(node *) malloc( sizeof(node)) ;
  printf("\n Enter data ");
  scanf("%d", &newnode -> data);
  newnode -> next = NULL;
  return newnode;
}

void push(node *newnode)
{
  node *temp;
  if( newnode == NULL )
  {
    printf("\n Stack Overflow..");
    return;
  }

  if(start == NULL)
  {
    start = newnode;
    top = newnode;
  }
 else
  {
    temp = start;
    while( temp -> next != NULL)
      {
        temp = temp -> next;
      }   
    temp -> next = newnode;
    top = newnode;
  }
     printf("\n\n\t Data pushed into stack");
}

void pop()
{
 node *temp;
 if(top == NULL)
 {
   printf("\n\n\t Stack underflow");
   return;
 }
 temp = start;
 if( start -> next == NULL)
  {
     printf("\n\n\t Popped element is %d ", top -> data);
     start = NULL;
     free(top);
     top = NULL;
  }
 else
 {
   while(temp -> next != top)
    {
      temp = temp -> next;
    }
   temp -> next = NULL;
   printf("\n\n\t Popped element is %d ", top -> data);
   free(top);
   top = temp;
 }
}
void display()
{
  node *temp;
  if(top == NULL)
  {
    printf("\n\n\t\t Stack is empty ");
  }
 else
  {
    temp = start;
    printf("\n\n\n\t\t Elements in the stack: \n");
    printf("%5d ", temp -> data);
    while(temp != top)
     {
       temp = temp -> next;
       printf("%5d ", temp -> data);
     }
  }
}

int menu()
{
 int choice;
 
 printf("\n \tStack operations using pointers.. ");
 printf("\n -----------**********-------------\n");
 printf("\n 1. Push ");
 printf("\n 2. Pop ");
 printf("\n 3. Display");
 printf("\n 4. Quit ");
 printf("\n Enter your choice: ");
 scanf("%d",&choice);
 return choice;
}
void main()
{
 int choice;
 node *newnode;
 do
 {
  choice = menu();
  switch(choice)
   {
    case  1: newnode = getnode();
              push(newnode);
              break;

    case  2: pop();
              break;
    
    case  3: display();
              break;
    
    case  4: return;

 }while( choice != 4 );
}

Prev Next

Share this

yashcode