Here's my solution..
Concept_Behind::
push(struct Stack* S,int data)::This function enqueue first element in Q1 and rest in Q2
pop(struct Stack* S)::if Q2 is not empty the transfers all elem's into Q1 and return the last elem in Q2
else(which means Q2 is empty ) transfers all elem's into Q2 and returns the last elem in Q1
Efficiency_Behind::
push(struct Stack*S,int data)::O(1)//since single enqueue per data
pop(struct Stack* S)::O(n)//since tranfers worst n-1 data per pop.
#include<stdio.h>
#include<stdlib.h>
struct Queue{
int front;
int rear;
int *arr;
int size;
};
struct Stack {
struct Queue *Q1;
struct Queue *Q2;
};
struct Queue* Qconstructor(int capacity)
{
struct Queue *Q=malloc(sizeof(struct Queue));
Q->front=Q->rear=-1;
Q->size=capacity;
Q->arr=malloc(Q->size*sizeof(int));
return Q;
}
int isEmptyQueue(struct Queue *Q)
{
return (Q->front==-1);
}
int isFullQueue(struct Queue *Q)
{
return ((Q->rear+1) % Q->size ==Q->front);
}
void enqueue(struct Queue *Q,int data)
{
if(isFullQueue(Q))
{
printf("Queue overflow\n");
return;}
Q->rear=Q->rear+1 % Q->size;
Q->arr[Q->rear]=data;
if(Q->front==-1)
Q->front=Q->rear;
}
int dequeue(struct Queue *Q)
{
if(isEmptyQueue(Q)){
printf("Queue underflow\n");
return;
}
int data=Q->arr[Q->front];
if(Q->front==Q->rear)
Q->front=-1;
else
Q->front=Q->front+1 % Q->size;
return data;
}
///////////////////////*************main algo****************////////////////////////
struct Stack* Sconstructor(int capacity)
{
struct Stack *S=malloc(sizeof(struct Stack));
S->Q1=Qconstructor(capacity);
S->Q2=Qconstructor(capacity);
return S;
}
void push(struct Stack *S,int data)
{
if(isEmptyQueue(S->Q1))
enqueue(S->Q1,data);
else
enqueue(S->Q2,data);
}
int pop(struct Stack *S)
{
int i,tmp;
if(!isEmptyQueue(S->Q2)){
for(i=S->Q2->front;i<=S->Q2->rear;i++){
tmp=dequeue(S->Q2);
if(isEmptyQueue(S->Q2))
return tmp;
else
enqueue(S->Q1,tmp);
}
}
else{
for(i=S->Q1->front;i<=S->Q1->rear;i++){
tmp=dequeue(S->Q1);
if(isEmptyQueue(S->Q1))
return tmp;
else
enqueue(S->Q2,tmp);
}
}
}
////////////////*************end of main algo my algo************
///////////////*************push() O(1);;;;pop() O(n);;;;*******/////
main()
{
int size;
printf("Enter the number of elements in the Stack(made of 2 queue's)::\n");
scanf("%d",&size);
struct Stack *S=Sconstructor(size);
push(S,1);
push(S,2);
push(S,3);
push(S,4);
printf("%d\n",pop(S));
push(S,5);
printf("%d\n",pop(S));
printf("%d\n",pop(S));
printf("%d\n",pop(S));
printf("%d\n",pop(S));
}
