Implement Queue using 2 stacks


Implement Queue using 2 stacks
Queue operations: EnQueue & DeQueue
Stack Operations: Push & Pop


Possible Solution:
The solution involves using one of the stacks as inbox stack. Incoming items are pushed onto this stack. The other stack is used as an outbox. When items need to be dequeued from the Queue and the outbox stack is empty, all the items from the inbox stack are popped and pushed on to the outbox stack. From there they can be popped until the outbox stack is empty. If the outbox is not empty then Dequeue operation is just a simple Pop() on the outbox stack.
C implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void EnQueue(int element)
{
 /* incoming elements go into this inbox stack */
 inboxStack.push(element);
}
 
int DeQueue()
{
 /* if the outbox stack has elements => pop from here */
 if(outboxStack.Count > 0)
 {
  return outboxStack.Pop();
 }
 else
 {
  /* move all elements from the inbox stack to the outbox stack */
  while(inboxStack.Count > 0)
  {
   outboxStack.Push(inboxStack.Pop());
  }
  if(outboxStack.Count > 0)
  {
   return outboxStack.Pop();
  }
 }
}

0 comments:

Post a Comment