Stack implementation using linked list

A stack data structure is a versatile data structure which is useful whenever we want output to be reverse of input, or we want a LIFO - last in first out behavior

Image from Wikipedia

.

A function call in most languages employs a stack. The parameters and local variables are pushed to call stack. And a return statement pops out most recent call stack.

Similarly when we want to check if an expression has balanced brackets, we can use a stack to store brackets.

Top of stack:

 Unlike a linked list where elements can be added to the end of list or beginning of a list, values are always added to the top of the stack. Just like a plate is added to the top of a stack of plates.

And a value is always removed from top of the stack - similar to a stack of plates again.

A stack abstract data type should define three functions

1. push - push function inserts a value at the top of stack 
2. pop - pop function removes a value from top of stack
3. isempty - isempty function checks if the stack is empty
4. peek or top - this gives the value at the top of stack

Implementation

A stack can be implemented using an array or a linked list. In both these implementations, all of the 4 functions will have O(1) time complexity. In array implementation top will be the index in array.

Let us look at linked list implementation of a stack

Linked List implementation:

In linked list implementation of stack, top of stack can be a node pointer just like head. And to push a value to stack, a node should be added to beginning of list.

NODEPTR push(NODEPTR top,NODEPTR newnode)
{ 
     newnode->next = top;
     top = newnode;
     return top;
}

To pop a value from stack, a node must be deleted from beginning of linked list.

int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
       return ERROR;
   int num = (*topPtr)->n;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}

And checking whether the stack is empty is just checking if top is NULL.

int isempty(NODEPTR top)
{
   return top==NULL;
}

 Here is the driver  program.

#include<stdio.h>  
#include<stdlib.h>
#define ERROR -1000
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR push(NODEPTR top,NODEPTR newnode)
 { 
     newnode->next = top;
     top = newnode;
     return top;
}
int isempty(NODEPTR top)
{
   return top==NULL;
}
int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
       return ERROR;
   int num = (*topPtr)->n;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}

 int main()  
 {  
     NODEPTR top = NULL;
     NODEPTR nd;

     while(1)
     {  
       int option,value; 
       printf("Enter 1- push 2- pop 3 - exit"); 
       scanf("%d",&option);
       if(option==3)
          break;
       switch(option)
       {
           case 1:  printf("new value to push=");  
             scanf("%d",&value);  
             nd = create_node(value);  
                    top = push(top,nd);
                    break;
           case 2:  value = pop(&top);
                    if(value==ERROR)
                         printf("Stack empty\n");
                    else
    printf("Value popped is %d\n",value);
                    break; 
        }  
    }     
 }