CareerCup

Queue can be implemented using two stacks, but either Enqueue or Dequeue is expensive

Steps:
1. Create stacks s1 and s2
2. Enqueue operation - push data into s1 then pop all items from s1 and push it into s2
3. Dequeue operation - pop from s2

import java.util.Stack;


public class QueueByStacks {
	Stack<Integer> master;
	Stack<Integer> slave;
	
	
	public QueueByStacks() {
		super();
		master = new Stack<Integer>();
		slave = new Stack<Integer>();
	}

	public void enque(int element){
		master.add(element);
	}
	
	public Integer deque(){
		if(slave.isEmpty()){
			while(!master.isEmpty()){
				slave.add(master.pop());
			}
		}else{
			return slave.pop();
		}
		if(slave.isEmpty()){
			return null;
		}else{
			return slave.pop();
		}
	}
	
	public static void main(String[] args) {
		QueueByStacks queue = new QueueByStacks();
		queue.enque(3);
		queue.enque(4);
		System.out.println(queue.deque());
		queue.enque(5);
		System.out.println(queue.deque());
		System.out.println(queue.deque());
		System.out.println(queue.deque());
	}

}

class Queue {
public:
	int top();
	int dequeue();
	void enqueue(int v);
	int size();
private:
	bool uprightStackActive;
	stack<int> uprightStack;
	stack<int> reverseStack;
	void copy(stack<int>& from, stack<int>& to) {
		while(from.size() > 0) {
			to.push(from.top());
			from.pop();
		}
	}
};

int Queue::top() {
	if(uprightStackActive) {
		copy(uprightStack, reverseStack);
		uprightStackActive = false;
	} 
	return reverseStack.top();
}
int Queue::dequeue() {
	if(uprightStackActive) {
		copy(uprightStack, reverseStack);
		uprightStackActive = false;
	} 
	auto ret = reverseStack.top();
	reverseStack.pop();
	return ret;
}
void Queue::enqueue(int v) {
	if(!uprightStackActive) {
		copy(reverseStack, uprightStack);
		uprightStackActive = true;
	}
	uprightStack.push(v);
}
int Queue::size() {
	return uprightStack.size() + reverseStack.size();
}

test

test