In this tutorial, we are going to solve or make a solution of Queue using the Two Stacks problem. so first we need to implement a queue using two stacks. and then we need to perform three queries on the stack. first en queue an element, de queue the element at the front of the queue. after that print the element at the front of the queue.
Problem solution in 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])
Problem solution in 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 rear=-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]); } } } }
Problem solution in 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; }
Problem solution in 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]); }
Problem solution in 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); });
The Javascript solution doesn't use two stacks.
It takes too long (for some test cases) to use two stacks, which makes the runtime complexity to be only enqueue = O(n) and dequeue = O(1) OR only dequeue = O(n) and enqueue = O(1), rendering the solution incomplete.
Yeah unfortunately this is what I experienced as well