## Algorithm

Problem Name: Data Structures - Queue using Two Stacks

In this HackerRank in Data Structures - Queue using Two Stacks solutions

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 q queries, where each query is one of the following 3 types:

1. `1 x`: Enqueue element x 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.

Input Format

The first line contains a single integer, q denoting the number of queries.
Each line i of the q subsequent lines contains a single query in the form described in the problem statement above. All three queries start with an integer denoting the query type , but only query 1 is followed by an additional space-separated value, x , denoting the value to be enqueued.

Constraints

• 1 <= q <= 10**5
• 1 <= type <= 3
• 1 <= |x| <= 10**9
• It is guaranteed that a valid answer always exists for each query of type 3.

Output Format

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

Sample Input

```STDIN   Function
-----   --------
10      q = 10 (number of queries)
1 42    1st query, enqueue 42
2       dequeue front element
1 14    enqueue 42
3       print the front element
1 28    enqueue 28
3       print the front element
1 60    enqueue 60
1 78    enqueue 78
2       dequeue front element
2       dequeue front element
```

Sample Output

``````14
14``````

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void enqueue(int);
void dequeue();
void print_ele();

int front=-1,rear=-1, size = 1000000;
int a[1000000];

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int q, choice;
scanf("%d",&q);
while(q-->0){
scanf("%d",&choice);
switch(choice){
case 1:{
int ele;
scanf("%d",&ele);
enqueue(ele);
}break;
case 2:{
dequeue();
}break;
case 3:{
print_ele();
}break;
}
}

return 0;
}

void enqueue(int x){
if(front==-1 && rear==-1){
front++;
rear++;
a[front]=x;
}
else if((front==0 && rear==size-1) || front==rear+1)
printf("Queue full \n");
else if(rear==size-1)
rear=-1;
else
a[++rear]=x;
}

void dequeue(){
if(front==rear==-1)
printf("empty queue \n");
else if(front==size)
front=0;
else if(front==rear){
front=-1;
rear=-1;
}

else
front++;

}

void print_ele(){
if(front==rear==-1)
printf("Queue empty \n");
else
printf("%d \n",a[front]);
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
stack < int> s1, s2;
int num_operations;
cin >> num_operations;
int Q_operation, x;
for(int i = 0; i  <  num_operations; i++){
cin >> Q_operation;
if(Q_operation == 1){
cin >> x;
s1.push(x);
}
if(Q_operation == 2){
if(!s2.empty()){
s2.pop();
}
else{
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
s2.pop();
}
}
if(Q_operation == 3){

if(!s2.empty()){
cout << s2.top() << endl;
}
else{
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
cout << s2.top() << endl;
}
}
}

return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int arr[] = new int[n];
int rea r= -1;
int front = 0;
for(int i = 0; i  <  n; i++)
{

int ops = in.nextInt();
if(ops == 1)
{
int num = in.nextInt();
arr[++rear] = num;
}
else if (ops == 2)
{
int num = arr[front++];
}
else
{
System.out.println(arr[front]);
}
}

}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function processData(input) {
//Enter your code here
var lines = input.split("\n");
var count = +lines[0];
var queue = [];
for (var i = 1; i  < = count; i++) {
var args = lines[i].split(' ');
var cmd = +args[0];
var arg;
switch (cmd) {
case 1:
arg = args[1];
queue.push(arg);
break;
case 2:
queue.shift();
break;
case 3:
console.log(queue[0]);
break;
}
}
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
old, new = [], []
for _ in range(int(input())):
val = list(map(int,input().split()))
if val[0] == 1:
new.append(val[1])
elif val[0] == 2:
if not old :
while new : old.append(new.pop())
old.pop()
else:
print(old[-1] if old else new[0])
``````
Copy The Code &
Advertisements