Stacks

1. The collection of homogeneous data items where deletion or insertion of item takes place only in the last position, i.e called the TOP of the stack :LIFO approach [Last in First Out]
2. These are also homogeneous along with
   • Arrays
   • Standard Linked lists
   • Stacks
   • Queues

   Non-homogeneous

   • Generic Linked lists[using void* or templates/polymorphism] different data types are stored in different nodes
   • Struct
   • Union
   • Union
   • JSON/XML
   • Objects in python/java

Code for Implementing Stack as ADT

  

#include<stdio.h>

int n,top=-1;
int s[];

void  display(){
  printf("\nUpdated Stack:\n");
  for(int i=top;i>=0;i--){
    if(i==top){
      printf("%d -- top\n",s[i]);
    }else{
    printf("%d\n",s[i]);
    }
  }

}

void push(){
  if(top>=n-1){
    printf("\nOverflow condition!");
    return;
  }else{
    int item;
    printf("\nEnter the item to be inserted: ");
    scanf("%d",&item);
    s[++top]=item;
  }
  display();
}


void create(){
  printf("\nEnter the size of the stack: ");
  scanf("%d",&n);
  char ch='y';
  while(1){
  if(ch=='y'){
     if(top>=n-1){
      printf("\n Overflow Condition! ");
      display();
      return;
    }
    push();
    printf("\nDo you want to enter the data?[y/n]: ");
    scanf(" %c",&ch);
  }else{
    display();
    return;
  }
  }

}



void  pop(){
  printf("\n\nPerforming pop operation!\n");
  printf("\nPopped element is: %d",s[top--]);
}

void  length(){
  printf("\n The length of the stack right now is :%d",top+1);
}

int main(){
  create();
  printf("\n\nPerforming push operation!\n");
  push();
  pop();
  display();
  length();

}
  
  

Recursion

Types

1. Direct

   A function that calls itself

2. Indirect

   The function the calls other which which calls the the earlier function itself.

Introduction

Save the formal parameters, local variables and return address

Body of the function

1. Stopping condition
2. condition to enter certain step to perform execution
3. else condition on recursive calls with function parameter defination

Recursion code

Fibonacci Series

    

#include<stdio.h>

void fibi(){
  int n;
  printf("\nEnter the range: ");
  scanf("%d",&n);
  int arr[n];
  arr[0]=0;
  arr[1]=1;
  for(int i=2;i<=n;i++){
    arr[i]=arr[i-1]+arr[i-2];
  }
  for(int i=0;i<n;i++){
    printf("%d ",arr[i]);
  }
  return;
}

int fibr(int n){
  if (n==0)
    return 0;
  if (n==1)
    return 1;
  return (fibr(n-2)+fibr(n-1));
}

int main(){
  printf("\n\n Calling fibonacci iterative! \n");
  fibi();
  int n;
  printf("\n\n Calling fibonacci recursive! \n");
  printf("\nEnter the range: ");
  scanf("%d",&n);
  int i=1;
  while(i<=n){ 
    printf("%d ",fibr(i-1));
    i++;
  }
}
    
    

Factorial Code

#include<stdio.h>

void faci(){
  printf("\nEnter the range: ");
  int n;
  scanf("%d",&n);
  int arr[n];
  arr[0]=1;
  for(int i=1;i<n;i++){
    arr[i]=(i+1)*arr[i-1];
  }
  for(int i=0;i<n;i++){
    printf("%d ",arr[i]);
  }
}

int facr(int n){
  if(n==0){
    return 1;
  }
  return (n*facr(n-1));
}

int main(){
  printf("\nImpleting factorial using iterations! \n");
  faci();
  printf("\nImpleting factorial using recursion! \n");
  int res;
  printf("\nEnter the range: ");
  int n;
  scanf("%d",&n);
  int i=1;
  while(i<=n){
    printf("%d ",facr(i));
    i++;
  }
}
    

Tower of Hanoi

    

#include<stdio.h>

// only one disk can move at a time, from one pillar to another. 
// A larger disk cannot be placed on a smaller disk
// Only the top disc on any pillar may be moved to any other pillar.

int count=0;

void toh(int n,char s,char t,char d){
  if (n>0){
    toh(n-1,s,d,t);
    printf("\n Move disk %d %c->%c \n",n,s,d);
    toh(n-1,t,s,d);
  }
}

int main(){
  printf("\nEnter the number of discs: ");
  int n;
  char source='S',temp='T',destination='D';
  scanf("%d",&n);
  printf("\n Sequence is: ");
  toh(n,source,temp,destination);
}
    
    

GCD

    

#include<stdio.h>


int gcd(int n,int m){
  if(m==0){
    return n;
  }else if(n<m){
    return gcd(m,n);
  }
  else{
    return gcd(m,n%m);
  }
}

int main(){
  printf("\n Enter the number whose GCD you want to find: ");
  int n,m;
  scanf("%d%d",&n,&m);
  int result=gcd(n,m);
  printf("%d",result);
}
    
    

Advantages of Recursion

1. Recursino reduces the complexity of problems
2. Recursion allows the user to write much simpler and more legant programs
3. Program implemented by recusino will be smaller in length.
4. recusion programs can have any numbre of nesting levels.
5. The recusion technique is more natural and compact.
6. Recusion is a top-down programming tool,where the given problem is diviled into smaller modules,each module are then individually attached.

Applications of Stack

1. Recusion
2. Recersal of a string
3. Checking the parenthesis matching
4. Postfix expression evaluation
5. infix to postfix conversion
6. infix to prefix conversion