Given queue data structure and we need to implement a stack using only given queue data structure. The assumption is that that we can find the size of the queue at any point.
The idea is to keep newly inserted element always at the front, keeping the order of previous elements same. Below are complete steps.
// e is the element to be pushed and s is stack
push(s, e)
1) Enqueue e to q
2) One by one Dequeue s items from queue and enqueue them except ‘e’.
// Removes an item from the stack
pop(s)
1) Dequeue an item from q
package com.stackqueue;
import java.util.LinkedList;
import java.util.Queue;
/**
* Implement stack using <B>only</B> given queue data structure.
*
*
* We need to focus on the insertion logic of the element.
* Newly inserted element always at front, keeping order of previous elements same.
*
* Steps# (x is the element to be pushed and s is stack)
* push(s, x)
* Let size of q be s.
* 1) Enqueue x to q
* 2) One by one Dequeue s items from queue and enqueue them.
*
* pop(s) : Removes an item from stack
* 1) Dequeue an item from q
*
* @link https://www.geeksforgeeks.org/implement-a-stack-using-single-queue/
*
* @author rajesh dixit
* @since May 2, 2018 4:30:58 PM
*/
public class ImplementStackUsingSingleQueue {
private static class Stack<E> {
/** Queue, which is used to store the stack element. */
Queue<E> queue = new LinkedList<>();
/**
* Returning the peek element of the Stack.
* @return
*/
public E peek() {
return queue.peek();
}
/**
* Returning the front of Queue.
*
* @return top element of the Stack.
*/
public E poll() {
return queue.poll();
}
/**
* Adding element at rear and to achieve LIFO, polling front from queue and adding it to rear.
*
* @param value
* @return true on add of element
*/
public boolean push(E value) {
boolean result = queue.add(value);
for (int i = 0; i < queue.size() - 1; i++) {
E element = queue.poll();
queue.add(element);
}
return result;
}
}
/**
* Driver method
*
* @param args
*/
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int e1 = stack.poll();
System.out.println(e1);
stack.push(4);
e1 = stack.peek();
System.out.println(e1);
}
}
