Stack Data Structure with PUSH,POP and STACK-EMPTY Algorithm and Code in C

By -

Stack Data Structure

Stacks are data structures that follow the Last In First Out (LIFO) principle or First in last out(FILO) . The last item to be inserted into a stack is the first one to be deleted from it.

For example, you have a stack of trays on a table. The tray at the top of the stack is the first item to be moved if you require a tray from that stack.

Inserting and deleting elements

Stacks have restrictions on the insertion and deletion of elements. Elements can be inserted or deleted only from one end of the stack from the top. The element at the top is called the top element.
 The operations of inserting element is called push() and deleting elements is called pop().
When the top element of a stack is deleted, if the stack remains non-empty, then the element just below the previous top element becomes the new top element of the stack.
For example, in the stack of trays, if you take the tray on the top and do not replace it, then the second tray automatically becomes the top element (tray) of that stack.





Size of stack changes with each push and pop operation. Each push
increases size of the stack by 1 and pop operation decreases the size of the stack by 1.

Application of stack

  • Recursion
  • Infix to postfix conversion
  • Parsing:- matching pattern, match tags < >
  • Browser
  • Editors
  • Tree Traversal
  • Graph Traversal

  Stack Operations

When top of stack = 0, stack contain no elements and is empty.   Then we can check by STACK-EMPTY operation. If empty stack is popped, then we can say stack underflow.  
If top of stack exceed the MAX size, the stack is overflow. 

ALGORITHMS for PUSH and POP operations
 STACK-EMPTY(S) 
  1. if top[S]=0                                  //S = Stack
  2.     then return TRUE
  3.     else return FALSE  
PUSH(S,item)                                //item to be inserted in stack
  1. top[S] <--- top[S] +1
  2. S[top[S]] <--- item
 POP(S)
  1. if STACK-EMPTY(S)
  2.     then return "underflow" 
  3.     else top[S] <--- top[S]-1
  4.          return S[top[S]+1]

 Stack using Array:

push(insertion) operation:

int stack[MAX];
int top=-1;
void push(int item)
{
    if(top==MAX-1)
       {
           printf("Overflow");
        }
    else
       {
         stack[++top]=item;
        }
   return;
} 

pop(deletion) :

int pop()
{
    int temp;
    if(top==-1)
     {
        printf("Underflow");
        return =-1;
     }
   else
      {
          temp=stack[top--];
      }
     return temp;
 } 

Stack Using linked list:

push(insertion):

struct node
 {
   int i;
   struct node *link;
 };
push(int item)
{
   struct node *p=(struct node*)malloc(sizeof(struct node));
   if(p==NULL)
   {
     printf("Error of malloc"); 
     return;
    }
   p->data=item;
   p->link=head;
   head=p;
}

pop(deletion) :

  struct node

 {
   int i;
   struct node *link;
 };

  int pop()
  {
   int item;
   struct node *p;
   if(head==NULL)
   {
     printf("Underflow");
     return -1;
    }
  item=head->i;
  p=head;
  head=head->next;
  free(p);
  } 

   

  

Comments

Post a Comment

Popular posts from this blog

C program that contains a string XOR each character in this string with 0 ,127

By -
Write a C program that contains a string (char pointer) with a value \Hello World’. The program should XOR each character in this string with 0 and displays the result. Program: #include<stdlib.h> main() { char str[]="Hello World"; char str1[11]; int i,len; len=strlen(str); for(i=0;i<len;i++) { str1[i]=str[i]^0; printf("%c",str1[i]); } printf("\n"); } Q.2 Write a C program that contains a string (char pointer) with a value \Hello World’. The program should AND or and XOR each character in this string with 127 and display the result. PROGRAM: #include <stdio.h> #include<stdlib.h> void main() { char str[]="Hello World"; char str1[11]; char str2[11]=str[]; int i,len; len = strlen(str); for(i=0;i<len;i++) { str1[i] = str[i]&127; printf("%c",str1[i]); } printf("\n"); for(i=0;i<len;i++) { str3[i] = str2[i]^127; printf("%c",str3[i]); } pri
Read more

Queue in Data Structure(DS)

By -
Image
Queue Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back(rear) and removed from the front. Think of it as  a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.   Basic features of Queue Like a stack, the queue is also an ordered list of elements of similar data types. A queue is a FIFO( First in First Out ) structure. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue  must be removed, to remove the new element. In a simple queue, there is a disadvantage after deleting element we cannot insert the element in the queue because of insertion  is possible from the rear but deletion is performed from the front.                                           insertion                                     ------------------
Read more

Implementation of stack Using Array

By -
Implementation  of stack Using Array #include<stdio.h> void pop(); void push(); void display(); int i,n,ch=0,top,item,stack[50]; int main() {     printf("Enter the number of element in Stack:\t");     scanf("%d",&n);     top=-1;     printf("Stack Operations");     printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");    do     {         printf("Enter the choice: ");         scanf("%d",&ch);         switch(ch)         {             case 1:push();                    break;             case 2:pop();                    break;             case 3:display();                    break;             case 4:exit(0);                    break;             default:printf("!!Wrong choice!!\n");         }     }     while(ch!=4);     return 0; } void push(int item) {     if(top==n-1)         printf("Overflow\n");     else     {        
Read more