Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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 x: Enqueue element x into the end of the queue.2: Dequeue the element at the front of the queue.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
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]);
}
#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;
}
#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]);
}
}
}
}
#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);
});
#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])