### Queue using stack queue stack stackqueuelinkedlist    Posted: 5 years ago Edit answers (1) views (5438)

Implement a queue data structure using only two given stacks.

 Posted: 5 years ago 0 1 Edit Let the two given stacks be named as $$stack1$$ and $$stack2$$. The algorithm to implement a $$queue$$ by using two $$stacks$$ works as : Enqueue : Push elements to $$stack1$$. Dequeue : If $$stack2$$ is not empty, pop elements from $$stack2$$. $$\hspace{16mm}$$ Otherwise, pop elements from $$stack1$$ and push them to $$stack2$$ first. Then, pop elements from $$\hspace{16mm}$$ $$stack2$$. Time complexity for $$enqueue$$ operation is $$O(1)$$ whereas for $$dequeue$$ operation $$O(n)$$. $$\therefore$$ Overall time complexity is $$O(n)$$.public class implementQueueUsingStacks { /* two stacks - stack1 and stack2 */ private Stack stack1 = new Stack (); private Stack stack2 = new Stack (); /* Enqueue - add the element in stack1 */ public void enqueue(int element) stack1.push(element); /* Dequeue - remove the element from stack2 */ public E dequeue(){ if (stack2.isEmpty()){ while (!stack1.isEmpty()) stack2.push(stack1.pop()); } return stack2.pop(); } }