Stack using queue
  • queue
  • stack
  • stackqueuelinkedlist
  •   
  • Posted: 1 year ago
  • Updated: 11 months ago
  • Edit
  • answers (1)
  • views (193)

Implement a stack data structure using only two given queues.


Posted Answers

Let the two given queues be named as \( queue1 \) and \( queue2 \). The algorithm to implement a \( stack \) by using two \( queues \) works as :


  • Push : Enqueue elements to \( queue1 \).
  • Pop : Dequeue all the elements except the last one from \( queue1 \) into \( queue2 \).
    \( \hspace {8.0mm} \) Return the last element of \( queue1 \).
    \( \hspace {8.0mm} \) Interchange the names of \( queue1 \) and \( queue2 \).



Time complexity = \( O(n) \).

public class implementStackUsingQueues   {

/* two queues - queue1 and queue2 */
private Queue queue1 = new LinkedList ();
private Queue queue2 = new LinkedList ();

/* push : add the element in queue1 */
public void push(int element)
queue1.enqueue(element);

/* Pop : Move all the elements except the last one from queue1 into queue2
and remove the last element in queue1 */
public int pop(){

/* copying all but last element from queue1 into queue2 */
while( queue1.size() != 1){
int element = queue1.dequeue();
queue2.enqueue(element);
}

/* Return the last element of queue1 */
int element = queue1.dequeue();

/* Interchange queue1 and queue2 */
while( !queue2.isEmpty() )
queue1.enqueue(queue2.dequeue());

/* Return the popped element */
return value;

}
}

You need to Sign In to post your solution.