Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Template<typename T> Class StackQueue
{
stack<T> EnQStack; //stack to use for enqueue operation
stack<T> DQStack; //stack to use for dequeue operation
public:
void enQ(T data)
{
EnQStack.Push(data);
}
T deQ()
{
//this means that the DQStack is empty, in this case need to transfer contents from EnQStack to DQStack
if (DQStack.Empty()) then TransferStack(EnQStack,DQStack);
return DQStack.Pop();
}
void TransferStack(stack<T> From, stack<T> To)
{
T data;
while (!From.empty())
{
data = From.Pop();
To.Push(data);
}
}
}
The following question was: This algorithm does work in the intended way, but what is your argument to that it will always work?
Means... how do you explain that pop from one stack and push into another will always give us a Queue functionality?
i think we would also be needing a temporary stack
imagine a situation where we have stack 2 full and stack 1 not full
now even though we have space left we cant utilize it
so for such situations we need to transfer whole of stack 2 to temp stack
pop it and transfer it to stack1 till its full
and transfer back the remaining elements to stack2
i think we would also be needing a temporary stack
imagine a situation where we have stack 2 full and stack 1 not full
now even though we have space left we cant utilize it
so for such situations we need to transfer whole of stack 2 to temp stack
pop it and transfer it to stack1 till its full
and transfer back the remaining elements to stack2
1 # !/usr/bin/python
2 # -*- encoding: utf-8 -*-
3
4 class DoubleStackQueue:
5
6 def __init__(self):
7 self.first_stack = []
8 self.second_stack = []
9
10 def en_queue(self, el = None):
11 self.first_stack.append(el)
12
13 def de_queue(self):
14 if len(self.second_stack) == 0:
15 while len(self.first_stack) != 0:
16 self.second_stack.append(self.first_stack.pop())
17 return self.second_stack.pop()
18
19 if __name__ == '__main__':
20 queue = DoubleStackQueue()
21 queue.en_queue(1)
22 queue.en_queue(2)
23
24 print queue.de_queue()
25 print queue.de_queue()
26
27 queue.en_queue(3)
28 print queue.de_queue()
Use two stacks:
- Sara April 02, 2012For deQ if the 1st stack is empty, check the 2nd stack and do a pop from the 2nd and push into the 1st until 2nd stack is empty. When done or if 1st stack is not empty pop the first element and return it.
For enQ always push into the 2nd stack and if is full then do another round of push/pops and then do a push.