Tuesday, 3 May 2011

Queue with two stacks

Implement a queue using two stacks. The operations need not be neccesarily O(1).





/* Include Stack Implementation (using Array)*/
#include "stackimplarray.h"

void queuepush(STACK* st1, STACK* st2, int val)
{
/* If first stack is empty, push the value straight down */
if (st1->size == 0)
{
st1->items[st1->size++] = val;
return;
}

/* Pop all elements of first stack
and push it into second stack */
while(st1->size != 0)
{
push(st2, pop(st1));
}

/* Push value onto second stack */
push(st2, val);

/* Pop all elements of second stack
and push it into first stack */
while(st2->size != 0)
{
push(st1, pop(st2));
}
}


/* Driver code to test above functions*/
int main()
{
STACK stack1, stack2;
int i;
for(i=1; i<=10; i++)
{
queuepush(&stack1, &stack2, i * 100);
}

while(stack1.size != 0)
{
printf("%d\n", pop(&stack1));
}
}



No comments:

Post a Comment