program 70: stack with doubly linked list

The need:
    This program was written just to show how definitions of push() and pop() vary as the element structure is changed. This program also provide you a fully functional interactive console to do some operations on stack.
The code:
---------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
// defining data-type node
struct linked_list
{
    int num;
    struct linked_list *next, *prev;
} ;
typedef struct linked_list node ;
//declaration of functions
node *push(node *top,int j);
int pop(node *top);
void display(node *top);
void rev_display(node *top);
main()
{
    int i,j;
    node *top=NULL ;
    while(1)
    {
      printf("\nEnter your choice :");
      printf("\n1. Push. Dont push 0");
      printf("\n2. Pop");
      printf("\n3. Display top to bottom");
      printf("\n4. Display bottom to top");
      printf("\n5. Exit\n");
     scanf("%d",&i);
        switch(i)
        {
            case 1 :
            scanf("%d",&j);
            top=push(top,j);
            break;
            case 2:
            j=pop(top);
            if(j)
            printf("Element popped is => %d\n",j);
            break;
            case 3:
            display(top);
            break;
            case 4:
            printf("Elements in the stack (bottom to top) are :\n");
            rev_display(top);
            break;
            case 5:
            exit(0);
            default:
            printf("Invalid choice !!!\n\n");
        }
    }
}
/*Inserting the elements using push function*/
node *push(node *top,int j)
{
  node *m;
  m=(node *)malloc(sizeof(node));
  m->num=j;
  m->next=top;
  m->prev=NULL;
  if(top)
  top->prev=m;
  return(m);
}
/*Removing the elements using pop function*/
int pop(node *top)
{
int j;
node *temp=top;
  if(temp==NULL)
  {
    printf("\nSTACK is Empty!!!\n");
  }
  else
  {
  j=top->num;
  temp=top->next;
  temp->prev=NULL;
  free(top);
  top=temp;
    return (j);
  }
return 0;
}
/*Displaying the elements */
void display(node *top)
{
  node *pointer=NULL;
  int j=0;
  pointer=top;
  if(top)
  {
  printf("Elements in the stack (top to bottom) are :\n");
  while(pointer!=NULL)
  {
    printf("%d-->",pointer->num);
    pointer=pointer->next;
    j++;
    if(j>20)
    break;
  }
  printf("END\n\n");
 }
else
printf("Stack is empty !!!\n");
}
void rev_display(node *top)
{
  node *p1=NULL,*p2=NULL;
  p1=top;
  while(p1!=NULL)
  {
  p2=p1;
    p1=p1->next;
  }
    while(p2!=NULL)
  {
    printf("%d-->",p2->num);
    p2=p2->prev;
  }
  printf("END\n\n");
}

-----------------------------------------------------

program 69: stack implementation of linked list

The need:
    This program was written to get clear idea of stack concept. When I wrote program of previous post, I used to try to find physical existence of stack in the program. This program shows that stack is just an implementation not a physical thing like array. This program utilizes two common UDFs of stack implementation: 1. push() 2. pop(). This program only takes an element( here a number) form user and pushes on the top of an abstract stack. Then the program pops that element and prints back for user.
The code:
------------------------------------------------------

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MIN_INT 0x80000000
struct linked_list
{
int num;
struct linked_list *next;
};
typedef struct linked_list node;
void push(node **p,int x);
int pop(node **p);
main()
{
    int i,j;
    node *top=NULL;
    printf("Enter a natural number to push on stack.\n");
    scanf("%d",&i);
    push(&top,i);
    printf("%d pushed successfully\n",i);
    printf("now popping\n");
    j=pop(&top);
    printf("element popped is %d\n",j);
    return 0;
}
void push(node **p,int x)
{
    node *new_node;
    new_node=(node *)malloc(sizeof(node));
    new_node->num=x;
    new_node->next=*p;
    *p=new_node;
}
int pop(node **p)
{
    node *tmp=*p;
    int temp;
    if(tmp==NULL)
        return (MIN_INT);
    else
    {   
        *p=tmp->next;
        temp = tmp->num;
        free(tmp);
        return(temp);
    }
}

------------------------------------------------------
Remarks:
1. This program can be used for pushing any number of values. Here I needed some indication when the empty stack is asked for pop. In that case pop returns MIN_INT which is minimum possible value for integer. When on popping stack returns MIN_INT in main, we get to know that stack is actually empty.
2. Have a look on this program for some purposeful implementation of stack concept.

program 68: stack implementation of array

The need: 
   This is a program to reverse the string using stack. Though for reversing a string usually not done using stack, still this is a basic program to implement stack on an array.


The code:
----------------------------------------------------------

#define max 20
#include<stdio.h>
#include<string.h>
struct STACK
{
    int top;
    int str[max];
};
typedef struct STACK stack;
void push(stack *p,int x);
int pop(stack *p);
main()
{
    int i,j,s1[10],s2[10];
    stack st;
    st.top=-1;
    printf("Enter 10 numbers .");
    for(i=0;i<10;i++)
        scanf("%d",&s1[i]);
    printf("The string is :\n");
    for(i=0;i<10;i++)
    printf("%d ",s1[i]);
    for(i=0;i<10;i++)
        push(&st,s1[i]);
    for(i=0;i<10;i++)
        s2[i]=pop(&st);
    printf("\nThe reversed string is :\n");
    for(i=0;i<10;i++)
        printf("%d ",s2[i]);
}

void push(stack *p,int x)
{
    (p->top)++;
    p->str[p->top]=x;
}

int pop(stack *p)
{
    if(p->top=='\0')
    return (0);
    else
    return(p->str[p->top--]);
}

----------------------------------------------------------

Concept of Stack in C

      The stack is another type of data structure. This is analogous to a stack of pan cakes or sacs. One more thing I want to make clear about stack concept in C is that the stack is not a physical variable or object which you can point out in the program and say that this is my stack variable. I am emphasizing this because when I was learning for a whole month I wanted to see stack physically saying that yes this variable is stack while stack is not like that. This is an abstraction.
      Let me explain this in a simple way. You people may have seen stack ( a special vertically arranged pile) of sacs or cement bags. What those people do to make that stack is to put a bag initially and after that they go on putting one over the others to make a vertical pile ( the stack). Now when they want to remove the bag, they first remove the top most bag and proceed downward by removing bag by bag. So you can observe that the bag which was put last will be removed first and the bag which was put first will be removed last. This was the real life example of stack. In technical area also concept is exact same. We call this Last In First Out (LIFO) the stack concept. I have already told you people that stack is an abstraction. Its just the implementation of the real world stack concept onto our programs. In programming wherever we treat a bulk of elements in the same manner as cement bags we say that this is implementation of stack. We can implement stack in two ways:
1. Stack implementation in arrays.
2. Stack implementation in linked lists.


     To understand the stack concept in programming perspective you people need to know 4 terms: 
1. element : is a member of stack may be of a derived or built in datatype.
2. top: is the the variable which holds the index(in case of array) or address (in case of linked list) of top element.
3. push() : is the function to user defined push or put an element on stack.
4. pop() : is the user defined function to pop or remove an element from stack.


      Because the concept is same so 2 user defined functions push() and pop() are used in both the implementations. The definitions of push() and pop() are different for both implementations but the working is same as described above. Those definitions will be given in the upcoming programs.
To elaborate these implementations more programs will be put in next posts.


Remarks:
1. While programming you should not worry about the whole stack like where it resides, how to keep track of all elements etc. The stack is abstract thing. only thing you need to concentrate on and to keep track is the top.
2. Both the operations push() or pop() are concerned with top. The element put by push() on the stack always becomes the top and the pop() function also removes only the top element.
3. When pop removes the top element, the top variable points to next element which is now on the top.This is also true in real life examples of cement bags. when the topmost bag is removed we people see the bag just below the previous one is now at top.

ABCD pattern2

The need:

This program was asked by a reader.

The code:
---------------------------------------------------------

#include<stdio.h>
main()
{
    char z;
    int j,i,k;
    printf("Enter the number of rows..(1 to 26)\t");
    scanf("%d",&k);
    if(k<1||k>26)
    {
        printf("\nThe number entered was not in range of 1 to 26\n");
        printf("exiting...\n");
        exit(0);
    }
    printf("\n\n");
    for (i=0;i<k;i++)
    {
        z = 'A';
        for (j=0;j<k;j++)
        {   
            if(j<k-i)
            printf ("%c  ",z);
            else
            printf("_  ");
            z++;
        }
        z--;
        for (j=k;j>0;j--)
        {   
            if(j<=k-i)
            printf ("%c  ",z);
            else
            printf("_  ");
            z--;
        }
    printf("\n\n");
    }
}

--------------------------------------------------------- 

Output:

output of the program will be some thing like this:

sample output when input 8 is given.

A  B  C  D  E  F  G  H  H  G  F  E  D  C  B  A  

A  B  C  D  E  F  G  _  _  G  F  E  D  C  B  A  

A  B  C  D  E  F  _  _  _  _  F  E  D  C  B  A  

A  B  C  D  E  _  _  _  _  _  _  E  D  C  B  A  

A  B  C  D  _  _  _  _  _  _  _  _  D  C  B  A  

A  B  C  _  _  _  _  _  _  _  _  _  _  C  B  A  

A  B  _  _  _  _  _  _  _  _  _  _  _  _  B  A  

A  _  _  _  _  _  _  _  _  _  _  _  _  _  _  A  

program to reverse the digits of a given natural number

The need:
    This program was asked me by a reader of this blog.
The code:
-------------------------------------------------------

#include<stdio.h>
main()
{
    int number1,i,number2=0;
    printf("enter a natural number.\n");
    scanf("%d",&number1);
    if(number1<1)
    {
        printf("the number entered was not a natural number.\n");
        exit(0);
    }
    i=number1;
    while(i>0)
    {
        number2=10*number2+i%10;
        i=i/10;
    }
    printf("the reverse of %d number is %d\n",number1,number2);
}

-------------------------------------------------------

Calculating sum of digits of a natural number

The need:
    This program was asked me by a reader of this blog.
The code:
-------------------------------------------------------

#include<stdio.h>
main()
{
    int number,i,sum=0;
    printf("enter a natural number.\n");
    scanf("%d",&number);
    if(number<1)
    {
        printf("the number entered was not a natural number.\n");
        exit(0);
    }
    i=number;
    while(i>0)
    {
        sum+=i%10;
        i=i/10;
    }
    printf("sum of digits of %d is %d\n",number,sum);
}

-------------------------------------------------------

To print all prime numbers between two given numbers m and n

The need:
    This program was asked me by a reader of this blog. This program takes 2 numbers from the user and prints all the prime numbers between them (inclusive both the numbers).
The code:
-------------------------------------------------------

#include<stdio.h>
#include<math.h>
int isPrime(int );
main()
{
    int number1,i,number2;
    printf("enter a natural number.\n");
    scanf("%d",&number1);
    printf("enter second natural number.\n");
    scanf("%d",&number2);
    if(number1<1||number2<1)
    {
        printf("one of the numbers entered was not a natural number.\n");
        exit(0);
    }
    printf("the prime numbers between %d and %d are =>\n\n",number1,number2);
    for(i=number1;i<=number2;i++)
    {
        if(isPrime(i))
        {
            printf("%d\t",i);
        }
    }
    printf("\n\n");
}

int isPrime(int x)            //this function returns one if the
{                            //input number x is prime else returns 0
    int i,flag=1;
    if(x==1)   //people say 1 is not a prime number
     return 0;
    else if(x==2)  //people say 2 is a prime number
     return flag;
    else    //just following the definition for the number greater than 2
    for(i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

------------------------------------------------------- 

Remarks:

  If you are using linux/unix to compile this program, add '-lm'(without quotes) after the compile command. Ex. : if the file name is file.c, give the command:

"cc file.c -lm"(without quotes)
instead of only "cc file.c"

program 67: doubly linked list

The need:
      This program was written to learn how to use a doubly linked list. But the question come, "why is doubly linked list needed???" First of all I want to tell that the name doubly linked list comes from the fact that this linked is in deed connected doubly. Meaning is that each node has the address of its previous and next node unlike singly connected linked lists in which each node had address of its next node. So in singly connected linked lists we can traverse in only forward direction while in doubly connected inked list we can traverse in both directions. This is the need and plus point of doubly connected linked lists.




The code:
-----------------------------------------------------

// This a basic program to make a doublly linked list and to do some operation on it
#include<stdio.h.>
#include<stdlib.h>
// defining data-type node
struct linked_list
{
int num;
struct linked_list *next,*prev ;
} ;
typedef struct linked_list node ;
//declaration of functions
void create_list(node *p);
void sort(node *p);
void print(node *list);
void exchange(int *,int *);
main()
{
    int i;
    node *head ;
    head=(node *)malloc(sizeof(node));
    head->prev=NULL;
    printf("Enter a element numbers .\n");
    printf("Type -999 to end :\n");
    create_list(head);
    printf("The list created Successfully .\n");
    printf("The list is .\n");
    print(head);
    sort(head);
    printf("\nThe sorted list is .\n");
    print(head);
}
void create_list(node *list)
{
    scanf("%d",&list->num);
    if(list->num==-999)
        list->next=NULL;
    else
    {
        list->next=(node *)malloc(sizeof(node));
        list->next->prev=list;
        create_list(list->next);         //recursion
    }
}

void exchange(int *s1,int *s2)
{
    int temp;
    temp =*s1;
    *s1=*s2;
    *s2=temp;
}

void print(node *list)
{
    if(list->next!=NULL)
    {
    printf("%d-->",list->num);
    if(list->next->next==NULL)
        printf("END\n");
    print(list->next); //recursion
    }
}

void sort(node *list)
{
    node *p,*q;
    for(p=list;(p->next)!=NULL;p=p->next)
    for(q=list;(q->next->next)!=NULL;q=q->next)
    {
    if(q->num > q->next->num)
        exchange(&(q->num),&(q->next->num));
    }
}

-----------------------------------------------------
The approach:
    The approach is same as singly linked list. See there is a slight change in the structure of the datatype node and to keep track of *prev there are slight changes made in the UDFs also.