Microsoft Interview Question
Software Engineer / DevelopersIf there are no constraints on the memory usage, I would use 2 stacks -
1) For enqueue -
if(num_of_elem <=1)
push_stack1(element)
else
push_stack1(element)
while(top)
push_stack2(pop_stack1())
2) Dequeue -
while(element)
pop_stack2()
Here, the basic logic is push the elements in stack1 and keep a reverse order in stack2. This way you can perform the queue operations using the combination of push/pop from stack1 and stack2.
As SS said, this worked fantastically for me:
1 public class MyQueue<T> {
2 Stack<T> s1, s2;
3 public MyQueue() {
4 s1 = new Stack<T>();
5 s2 = new Stack<T>();
6 }
7
8 public int size() {
9 return s1.size() + s2.size();
10 }
11
12 public void add(T value) {
13 s1.push(value);
14 }
15
16 public T peek() {
17 if (!s2.empty()) return s2.peek();
18 while (!s1.empty()) s2.push(s1.pop());
19 return s2.peek();
20 }
21
22 public T remove() {
23 if (!s2.empty()) return s2.pop();
24 while (!s1.empty()) s2.push(s1.pop());
25 return s2.pop();
26 }
27 }
No need to push elements on to the second stack whenever a enqueue is requested. Just keep adding to first stack. When a dequeue is requested check if there are elements on stack2, if stack2 is empty keep popping from the first stack and placing them onto second stack until the requested number of pops.
- SS June 04, 2011Only thing need to remember is always dequeue happens from stack2 and enqueue happens in stack1.