Implement a queue using two stacks
Keep 2 stacks, let's call them inbox and outbox.
Queue:
- Push the new element onto inbox.
Dequeue:
- If outbox is empty, refill it by popping each
element from inbox and pushing it onto outbox
- Pop and return the top element from outbox.
Using this method, each element will be in each
stack exactly once - meaning each element will be pushed twice and popped
twice, giving amortized constant time operations.
package api.implement;
import java.util.Stack;
public class Queue<E> {
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item)
{
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
package api.implement;
public class TestQueue {
public static void main(String[]
args) {
Queue<String> queue = new Queue<String>();
queue.queue("rajesh");
queue.queue("sattu");
queue.queue("sattu1");
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
}
Output:
rajesh
sattu
No comments:
Post a Comment