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 Answers

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();
}

}

You need to Sign In to post your solution.