Implementation of stack as a linked list . Problem in pointers

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
  int data;
  struct node*link;

};

void push(struct node*,int);
int pop(struct node*);
void delstack(struct node*);

void main()
{ struct node*s = NULL;
  int i ;

  clrscr();

  push(s,14);
  push(s,-3);
  push(s,18);
  push(s,29);
  push(s,31);
  push(s,16);

  i=pop(s);
  printf("\n Item popped :%d",i);

  i=pop(s);
  printf("\n Item popped :%d",i);

  i=pop(s);
  printf("\n Item popped :%d",i);

  delstack(s);

  getch();

}

// Add a new node to the stack at the top of the linked list

void push(struct node*top,int item)
{ struct node*temp;
  temp=malloc(sizeof(struct node));

  if(temp==NULL)
  printf("\n Stack is full");


  temp->data=item;
  temp->link=top;
  top=temp;

}

// Pops an element from the stack

int pop(struct node*top)
{ struct node*temp;
  int item;
  if(top==NULL)
  {
   printf("\n Stack is empty ");
   return NULL;
  }
  temp=top;
  item=temp->data;
  top=top->link;

  free(temp);
  return item;
}

// Deallocates memory

void delstack(struct node*top)
{
  struct node*temp;

  if(top==NULL)
  return;


  while(top!=NULL)
  {
    temp=top;
    top=top->link;
    free(temp);

  }
}

My problem lies basically in the usage of pointers. This is the wrong program , The correct usage would have been with the double pointer top. but the point i dont understand is ' Is it possible to implement it without the double pointer. and if not , then why ?Why do we need a pointer to a pointer here.

The correct program is

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
  int data;
  struct node*link;

};

void push(struct node**,int);
int pop(struct node**);
void delstack(struct node**);

void main()
{ struct node*s = NULL;
  int i ;

  clrscr();

  push(&s,14);
  push(&s,-3);
  push(&s,18);
  push(&s,29);
  push(&s,31);
  push(&s,16);

  i=pop(&s);
  printf("\n Item popped :%d",i);

  i=pop(&s);
  printf("\n Item popped :%d",i);

  i=pop(&s);
  printf("\n Item popped :%d",i);

  delstack(&s);

  getch();

}

// Add a new node to the sta开发者_运维知识库ck at the top of the linked list

void push(struct node**top,int item)
{ struct node*temp;
  temp=malloc(sizeof(struct node));

  if(temp==NULL)
  printf("\n Stack is full");


  temp->data=item;
  temp->link=*top;
  *top=temp;

}

// Pops an element from the stack

int pop(struct node**top)
{ struct node*temp;
  int item;
  if(*top==NULL)
  {
   printf("\n Stack is empty ");
   return NULL;
  }
  temp=*top;
  item=temp->data;
  *top=(*top)->link;

  free(temp);
  return item;
}

// Deallocates memory

void delstack(struct node**top)
{
  struct node*temp;

  if(*top==NULL)
  return;


  while(*top!=NULL)
  {
    temp=*top;
    *top=(*top)->link;
    free(temp);

  }
}

If you didn't pass a pointer to the pointer, it would never be able to create or remove the first node of the list. That requires changing the value of your list pointer.

One common way to do is create a structure that holds a list header that always exists even if the list is empty.

struct Node {
  int data;
  struct Node *next;
};

struct List {
  struct Node *first;
};

Now you just create a List structure and pass it to push and pop. You can also throw in some handy elements like list length that pop and push update.

Try this and see if it helps. It will print "before". The parameter is copied so changing it in the function doesn't change it in the calling function. It would be the same for the head pointer to your list.

#include <stdio.h> 

void func(char *s) { 
  s="after"; 
} 

int main(int argc, char *argv[]) { 
  char *s="before"; 
  func(s); 
  printf("%s\n", s); 
} 

In a stack after the pop or push operation we need to alter the value of the stack top pointer, as the element at the top of the stack changes.

By your code node* s denotes the top of the stack.

Considering the push function,

void push ( node * top , int val ) 
{
   // formal parameter : node * top , int val ( let us assume the names )

   // Here we should create a new node ( say new_node ) as

   node * new_node = ( node * ) malloc ( sizeof( node ) ) ; 

   new_node->data = val ;
   new_node->link = top ;

   // now we need to set the top of the stack to this newly created node.

   top = new_node ;

}

However top being the formal parameter this change is not reflected in the actual parameter s and dies as soon as the function scope is exited.

Hence if we had passed the location of the stack head ( as &s ), the changes could have been made at this location and hence reflected.

A similar logic holds for the pop()

:)