♠ Posted by GeekyFry in algorithm,amazon-interview-question,data-structures,google-interview-question,interview,microsoft-interview-question,programming,queue,stack,tech-it at 9:00 PM

**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