Queues: A Tale of Two Stacks HackerRank Solution

Queues: A Tale of Two Stacks HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

• Enqueue: add a new element to the end of the queue.
• Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process queries, where each query is one of the following types:

1. 1 x: Enqueue element into the end of the queue.
2. 2: Dequeue the element at the front of the queue.
3. 3: Print the element at the front of the queue.

For example, a series of queries might be as follows:

Function Description

Complete the put, pop, and peek methods in the editor below. They must perform the actions as described above.

Input Format

The first line contains a single integer, , the number of queries.

Each of the next lines contains a single query in the form described in the problem statement above. All queries start with an integer denoting the query , but only query is followed by an additional space-separated value, , denoting the value to be enqueued.

Constraints

• It is guaranteed that a valid answer always exists for each query of types and .

Output Format

For each query of type , return the value of the element at the front of the fifo queue on a new line.

Sample Input

101 4221 1431 2831 601 7822

Sample Output

1414

Explanation

Source : https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Stack;
	public class Solution {
	public static void main(String[] args) {
	MyQueue<Integer> queue = new MyQueue<Integer>();
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	for (int i = 0; i < n; i++) {
	int operation = scan.nextInt();
	if (operation == 1) { // enqueue
	queue.enqueue(scan.nextInt());
	} else if (operation == 2) { // dequeue
	queue.dequeue();
	} else if (operation == 3) { // print/peek
	System.out.println(queue.peek());
	}
	}
	scan.close();
	}
	public static class MyQueue<Integer> {
	private Stack<Integer> stack1 = new Stack();
	private Stack<Integer> stack2 = new Stack();
	public void enqueue(Integer num) {
	stack1.push(num);
	}
	public Integer dequeue() {
	if (size() == 0) {
	return null;
	}
	if (stack2.isEmpty()) {
	shiftStacks();
	}
	return stack2.pop();
	}
	public Integer peek() {
	if (size() == 0) {
	return null;
	}
	if (stack2.isEmpty()) {
	shiftStacks();
	}
	return stack2.peek();
	}
	/* Only shifts stacks if necessary */
	private void shiftStacks() {
	if (stack2.isEmpty()) { // shifting items while stack2 contains items would mess up our queue's ordering
	while ( ! stack1.isEmpty()) {
	stack2.push(stack1.pop());
	}
	}
	}
	public int size() {
	return stack1.size() + stack2.size();
	}
	}
	}