Google Interview Question
Software Engineer InternsCountry: Brazil
Interview Type: In-Person
It is possible without using two stacks (technically making using of recursion stack)
#include <iostream>
#include <stack>
template <typename T>
class FIFO {
private:
std::stack<T> STACK;
public:
FIFO() {}
void enqueue(T val);
void dequeue();
T front();
};
template <typename T>
void FIFO<T>::enqueue(T val) {
STACK.push(val);
}
template <typename T>
void FIFO<T>::dequeue() {
if(STACK.empty()) { return; }
if(STACK.size()==1) {
STACK.pop();
return;
}
T tmp = STACK.top();
STACK.pop();
dequeue();
STACK.push(tmp);
}
template <typename T>
T FIFO<T>::front() {
if(STACK.size()==1) {
return STACK.top();
}
T tmp = STACK.top();
STACK.pop();
T value = front();
STACK.push(tmp);
return value;
}
int main() {
FIFO<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << queue.front() << std::endl;
queue.dequeue();
queue.enqueue(4);
std::cout << queue.front() << std::endl;
queue.dequeue();
std::cout << queue.front() << std::endl;
queue.dequeue();
std::cout << queue.front() << std::endl;
queue.dequeue();
return 0;
}
Use two stacks. One main to hold the values and an auxiliary stack.
To enqueue an item:
1. pop the whole stack and push it into the auxiliary.
2. push the new item into the main stack, pop the whole auxiliary stack and push it onto the main one.
This takes time proportional to 2N for enqueueing and constant to dequeue. You can make it more efficient by using more auxiliary stacks. E.g. with three stacks it takes N operations to enqueue. Still not optimal.
Two stocks:
- CT November 28, 20141) Enqueue by pushing into stack 1
2) Dequeue by popping from stack 2
3) ONLY when you dequeue and there is nothing in stack 2, lock both stacks and transfer all from stack 1 to stack 2 by popping-pushing. This is the worst case scenario for dequeue which is O(n) and the worst case scenario for enqueue if it has to wait for such lock. However, amortized time is constant O(1) for both, enqueue and dequeue
Believe it or not, this is useful. For instance, when there is an operation that exists for stock but not for queue. Such as, getting max in constant time.