How to implement queue using 2stacks???

implement the stack ADT using two queues
Hi I also have the same question can please someone help me?

I don't want to do homework (unless I am going to get a grade). But, I would be happy to help with feedback.

Why don't you all take a stab at it, and we can help you with feedback... or if you are having problems... tell us what the trouble is so we can help you understand.

As you like, so maybe that u can explain to me how to a class implement an interface in general, should my class "TwoQueueStack" for example implement all the methods of the interface for a stack?(size(), isEmpty(),top(), push(0), pop())?

if can also explain to me how is it possible that the first in can be the last out in teh case of two queues in cinema for example, i can't imagine that

Thanks

Any solution?
Hey all,

whatever happened to this? Just as it was to get interesting it got halted.

I've been asked the same question recently and the only way I could thing of was such that both push and pop would do the following:

copy the main queue into a temp queue one-element-by-one so that the order is reversed, then, either add or remove an element, then copy then do the reverse with the altered temp queue copied back to the main queue one-element-by-one so that the main queue is the reverse of the new 'altered' temp queue.

This way a LIFO stack can be implemented with the usage of 2 FIFO queues.

This will have the running-time for push & pop to O(2n) where as another storage type (i.e. list) would have the time of O(2n).

Is this right? is this the only way? is there another less timely way?

Any answer would help. well, any intelligent answer.

Not sure what you mean by copying the main queue to the temp queue so
that the elements would be reversed. If they are both queues, wouldn't
the order remain the same?

I think Kevin is accidentally saying "queue" when he means "stack". Other than that, his solution and his analysis seems correct.

I can't see any more efficient way to do (except that you probably don't need to move the final item).

I would be interested if there is a trick here that makes this problem interesting... but I sure don't see it.

Assuming he means to use stacks, the statement
"then, either add or remove an element"
is wrong for the "add" case.

If stack 3-2-1 becomes stack 1-2-3 and then you add an element,
you have have stack 4-1-2-3, which then becomes stack 3-2-1-4.
No?

Here are the steps for a dequeue().

1) Start with stack1 {3, 2, 1}.
2) pop off of stack1 and push on stack2 two times so that you have stack1 = {1} and stack2 = {2,3}
3) pop off of stack1 and and store as the return value.
4) pop off of stack 2 and push on to stack1 two times so that stack1 = {3,2} and stack2 is empty (this is the step you were missing.)
5) return the return value.

This leaves stack1 as {3,2} and the next enqueue() will push the value onto stack1 leaving {4,3,2}.

Right. That dequeues. But our poster said
"then, either add or remove an element".

I assume (yeah, yeah, I know; never assume)
that he meant "add" for enqueue and "remove"
for dequeue.

//Enqueue===> add
void add(int x,stack_type *st_ptr1 , stack_type *st_ptr2)
{
int item;
while(!(stack_empty(st_ptr2)))
{
pop(&item,st_ptr2);
push(item,st_ptr1);
}
push(x,st_ptr1);
}

//Dequeue==>delete
void delete(int *x , stack_type *st_ptr1 , stack_type *st_ptr2)
{
int item;
while(!(stack_empty(st_ptr1)))
{
pop(&item,st_ptr1);
push(item,st_ptr2);
}
pop(x,st_ptr2);
}

for compelete C program :: How to implement Queue using stack
see Edit [Moderator]: Link removed

itz easy only my dear....
to implement queue from 2 stacks, u use the 1st stack as the temp ... wat ever the element u ll going to push to the 1st stack immedietly pop them to the 2nd stack.... then u ll get FILO(first in last out) form on 2nd stack... itz nothing but Q.

this is using c

#include<stdio.h>
#include<conio.h>
#include<process.h>
int in_top=-1;
int out_top=-1;
void in_stack_push(int item);
int in_stack_pop();
void out_stack_push();
int out_stack_pop();
int insert_queue[20],delete_queue[20];

void main()
{
int i,ch,item;
clrscr();
while(1)
{
printf("\n1. Insert");
printf("\n2. Delete");

printf("\nEnter Your Choice:- ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the Element in Queue:- ");
scanf("%d",&item);
in_stack_push(item);
break;
case 2:
printf("Element Deleted:-%d",out_stack_pop());
break;
default:
printf("Thank You For using queue using two stack");
getche();
exit(0);
}
}
}
void in_stack_push(int item)
{
if(in_top>20)
printf("Queue Full");
else
insert_queue[++in_top]=item;
}
int in_stack_pop()
{
if(in_top>=0)
return insert_queue[in_top--];
}

void out_stack_push()
{
if(in_top==-1)
{
printf("Queue Empty");
}
else
{
while(in_top>=0)
delete_queue[++out_top]=in_stack_pop();
}
}
int out_stack_pop()
{
if(out_top==-1)
{
out_stack_push();
}
if(out_top<0 && in_top<0)
return 0;

if(out_top>=0)
return delete_queue[out_top--];
}

Assume two stacks stack1 and stack2.‎
I will use stack1 to store the queue elements and we can dequeue from it like queue.‎
And I will use stack2 as a temporary storage so that when enqueue object to ‎
stack(our queue implementation) I will pop all objects from stack1 and push them to stack2‎
‎ and then push the new object to stack1 and then pop all objects from stack2 and then push ‎
them back to stack1 .Algorithm will be like that:‎

Algorithm enqueue(o) ‎
Input: Object o
Output : Object o equeued into stack1‎
‎ If(stack1 is empty)‎
‎ Stack1.push(o)‎
While(stack1 is not empty)‎
‎ Stack2.push(stack1.pop())‎
‎ Stack1.push(o)‎
‎ While(stack2 is not empty)‎
‎ Stack1.push(stack2.pop())‎
‎ ‎
Algorithm dequeue()‎
Input : none
Output : dequeue the last inserted object from stack1‎
If(stack1 is empty)‎
‎ Throw exception
Return Stack1.pop() ‎
In this case we see that running time for dequeue is O(1) because it is just one operation getting the ‎last inserted object in the stack
And for enqueue is O(n) because we move all objects from one stack to the other and get them back.‎