Code:

#include "stdafx.h"
#include <iostream>
using namespace std;



struct stack
{
   int data;
   struct stack *ptr;
   struct stack *NextMinVal; //this is extra pointer as taken for next minimum value
};
///By this way, only 4 byte is extra per node.

struct stack *MinNode = NULL;  // this will point current mimimum node
struct stack *push(int data, struct stack * head);
struct stack *pop(struct stack * head);
void FindMinVal();

///**********************  it’s in O(1) time complexity*********************/
struct stack *push(int data, struct stack * head)
{
   struct stack *NewNode = (struct stack *) malloc(sizeof(struct stack));
   if (NewNode)
   {
      NewNode->data = data;
      NewNode->ptr = NULL;
      NewNode->NextMinVal = NULL;
      if (head != NULL)
      {
         NewNode->ptr = head;
         if (NewNode->data < MinNode->data)
         {
            NewNode->NextMinVal = MinNode;
            MinNode = NewNode;
         }
      }
      else
      {
         MinNode = NewNode;
      }
      printf("%d PUSHEDn", data);
   }
   return NewNode;
}

///**********************  it’s in O(1) time complexity*********************/
struct stack *pop(struct stack * head)
{
   if (head != NULL)
   {
      struct stack *temp;
      printf("POPED data is %dn", head->data);
      if (head->data == MinNode->data)
      {
         MinNode = head->NextMinVal;
      }
      temp = head;
      head = head->ptr;
      free(temp);
   }
   else
   {
      printf(" stack is emptyn");
   }
   return head;
}

///**********************  it’s in O(1) time complexity*********************/
void FindMinVal()
{
   if (MinNode != NULL)
   {
      printf("minimum value is %dn", MinNode->data);
   }
   else
   {
      printf("Thereis no data in stackn");
   }
}

///Take any test as you want....

int _tmain(int argc, _TCHAR* argv[])
{
   struct stack *head = NULL;
   head = push(10, NULL);
   head = push(7, head);
   head = push(3, NULL);
   head = push(13, head);
   FindMinVal();
   head = push(11, head);
   head = push(20, head);
   head = push(-4, head);
   head = push(0, head);
   head = push(-19, head);
   head = push(-15, head);
   head = push(-3, head);
   FindMinVal();
   head = pop(head);
   head = pop(head);
   head = pop(head);
   head = pop(head);
   FindMinVal();
   return 0;
}