Find the nearest smaller numbers on left side in an array

PROBLEM :

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.If no small element present on the left print -1.

Input:

The first line of input contains T test cases.

The first line of each test case contains the number of elements in the array.

The second line of each test case contains the elements of the array.

Output:

Print the n elements.
Constraints:

1<=T<=100

1<=N<=100

0<=A[i]<10000
Example:

Input:

2

3

1 6 2

6

1 5 0 3 4 5

Output:

-1 1 1

-1 1 -1 0 3 4

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

A Simple Solution is to use two nested loops. The outer loop starts from second element, the inner loop goes to all elements on left side of the element picked by outer loop and stops as soon as it finds a smaller element.
Time complexity of the above solution is O(n2).

There can be an Efficient Solution that works in O(n) time. The idea is to use a stack.

#include<iostream>
using namespace std;
#include<malloc.h>

typedef struct STACK
{
    int data ;
    struct STACK *next ;
}stack ;

void push_stack(stack **,int ) ;
int pop_stack(stack **) ;
int top_stack(stack **) ;

int main()
 {
int t,no,a[100],i,ele;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
   cin>>a[i] ;
 
   stack *s=NULL ;
 
   for(i=0;i<no;i++)
   {
       ele=top_stack(&s) ;
     
       while(ele>=a[i])
       {
            ele=pop_stack(&s) ;
            ele=top_stack(&s) ;
       }
       if(ele>a[i])
           cout<<-1<<" " ;
       else
           cout<<ele<<" ";
         
      push_stack(&s,a[i]) ;
   }
 
   cout<<endl ;
}
   
return 0;
}

void push_stack(stack **s,int ele)
{
    stack *temp ;
    temp=(stack*)malloc(sizeof(stack))  ;
    temp->data=ele ;
   
    temp->next=(*s) ;
    (*s)=temp ;
}

int pop_stack(stack **s)
{
    stack *temp ;
    if((*s)==NULL)
        return -1 ;
       
    temp=(*s) ;
    (*s)=temp->next ;
    int ch=temp->data ;
    free(temp) ;
    return ch ;
}

int top_stack(stack **s)
{
    if((*s)==NULL)
        return -1 ;
       
    return (*s)->data ;
}


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