Stack Data Structure

• Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).




• Main operations performed by a stack are :




1. Push : Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.




2. Pop : Removes an item from the top of the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.




3. Peek or Top : Returns top element of stack.




4. isEmpty : Returns true if stack is empty, else false




• Above operations viz. push(), pop(), isEmpty() and peek() all take O(1) time, as no loops are involved.




• Applications of stack :




1. Keeping track of function calls and return points. especially useful in a recursive function




2. Converting from infix to prefix or postfix.




3. Forward and backward feature in browsers.




• There are two ways to implement a stack :




1. Arrays




2. Linked List

Stack using Arrays

• Easy to implement. Memory is saved as pointers are not involved. However, Such a stack is not dynamic. It doesn’t grow and shrink depending on needs at runtime.




1. Step 1 : Create an array of a fixed capacity to store the stack elements. Create a variable named top to indicate array position at which element shall be inserted. Stack is empty when top is equal to -1 and stack is full when top is equal to last index.




2. Step 2 : To insert element in array for push() increment top by 1 and insert at the position.




3. Step 3 : To remove element from stack for pop(), use position top and then decrement it.

Demonstrate Stack using Array in C

• #include
  #include
  
  #define SIZE 10
  
  void push(int);
  void pop();
  void display();
  
  int stack[SIZE], top = -1;
  
  void main()
  {
     int value, choice;
     clrscr();
     while(1){
        printf("\n\n***** MENU *****\n");
        printf("1. Push\n2. Pop\n3. Display\n4. Exit");
        printf("\nEnter your choice: ");
        scanf("%d",&choice);
        switch(choice){
  	 case 1: printf("Enter the value to be insert: ");
  		 scanf("%d",&value);
  		 push(value);
  		 break;
  	 case 2: pop();
  		 break;
  	 case 3: display();
  		 break;
  	 case 4: exit(0);
  	 default: printf("\nWrong selection!!! Try again!!!");
        }
     }
  }
  void push(int value){
     if(top == SIZE-1)
        printf("\nStack is Full!!! Insertion is not possible!!!");
     else{
        top++;
        stack[top] = value;
        printf("\nInsertion success!!!");
     }
  }
  void pop(){
     if(top == -1)
        printf("\nStack is Empty!!! Deletion is not possible!!!");
     else{
        printf("\nDeleted : %d", stack[top]);
        top--;
     }
  }
  void display(){
     if(top == -1)
        printf("\nStack is Empty!!!");
     else{
        int i;
        printf("\nStack elements are:\n");
        for(i=top; i>=0; i--)
  	 printf("%d\n",stack[i]);
     }
  }
  

Stack using Linked List

• The linked list implementation of stack can grow and shrink according to the needs at runtime. However it Requires extra memory due to involvement of pointers.




1. Step 1 : Create a structure to represent the stack, it should have the attributes data and a pointer next.




2. Step 2 : Use a root pointer to refer to the stack top always.




3. Step 3 : Root pointer can be used to delete and insert nodes.

Demonstrate Stack using Linked List in C

• #include
  #include
  
  struct Node
  {
     int data;
     struct Node *next;
  }*top = NULL;
  
  void push(int);
  void pop();
  void display();
  
  void main()
  {
     int choice, value;
     clrscr();
     printf("\n:: Stack using Linked List ::\n");
     while(1){
        printf("\n****** MENU ******\n");
        printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d",&choice);
        switch(choice){
  	 case 1: printf("Enter the value to be insert: ");
  		 scanf("%d", &value);
  		 push(value);
  		 break;
  	 case 2: pop(); break;
  	 case 3: display(); break;
  	 case 4: exit(0);
  	 default: printf("\nWrong selection!!! Please try again!!!\n");
        }
     }
  }
  void push(int value)
  {
     struct Node *newNode;
     newNode = (struct Node*)malloc(sizeof(struct Node));
     newNode->data = value;
     if(top == NULL)
        newNode->next = NULL;
     else
        newNode->next = top;
     top = newNode;
     printf("\nInsertion is Success!!!\n");
  }
  void pop()
  {
     if(top == NULL)
        printf("\nStack is Empty!!!\n");
     else{
        struct Node *temp = top;
        printf("\nDeleted element: %d", temp->data);
        top = temp->next;
        free(temp);
     }
  }
  void display()
  {
     if(top == NULL)
        printf("\nStack is Empty!!!\n");
     else{
        struct Node *temp = top;
        while(temp->next != NULL){
  	 printf("%d--->",temp->data);
  	 temp = temp -> next;
        }
        printf("%d--->NULL",temp->data);
     }
  }    
  

Previous

Next