Queue using Two Stacks Hackerrank problem solution

Queue using Two Stacks Hackerrank

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<= 105
1<=type<=3 1<=|x|<= 109
It is guaranteed that a valid answer always exists for each query of type .

Output Format

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

Sample Input

10
1 42
2
1 14
3
1 28
3
1 60
1 78
2
2

Sample Output

14
14

Queue using Two Stacks Hackerrank

Solution
Solution using two stacks "old" and "new" in Python :
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])

Logic :
Always enque to new.
Always deque from old (point 3 if empty).
Transer all elements from new to old if old is empty (if need to dequeue).

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> Front,Rear;
    int Q;
    cin >> Q;
    while(Q--)
    {
        int type, x;
        cin >> type;
        if(type == 1)
        {
            cin >> x;
            Rear.push(x);
        }    
        else 
        {
           if(Front.empty())
           { // move all the elements from "Rear" stack to "Front" stack
               while(!Rear.empty())
               {
                   Front.push(Rear.top());
                   Rear.pop();
               }   
            }    
           if(!Front.empty())
           {
               if(type == 2) Front.pop();
               if(type == 3) cout << Front.top() << endl;
           }  
        }   
    }    
    return 0;
}
# Enter your code here. Read input from STDIN. Print output to STDOUT


front = []
back = []
def push_back():
    if back:
        return
    while front:
        item = front.pop(-1)
        back.append(item)


def enqueue(x):
    front.append(x)

def dequeue():
    push_back()
    back.pop(-1)




q = input()
for i in range(q):
    command_split = map(int, raw_input().split())
    if command_split[0] == 1:
        enqueue(command_split[1])
    elif command_split[0] == 2:
        dequeue()
    else:
        push_back()
        print back[-1]
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        LinkedList<Integer> l = new LinkedList<>();
        int q = in.nextInt();
        while (q-- > 0) {
            int type = in.nextInt();
            if (type == 1) {
                l.add(in.nextInt());
            }
            else if (type == 2) {
                if (!l.isEmpty()) {
                    l.pollFirst();
                }
            }
            else {
                System.out.println(l.getFirst());
            }
        }
    }
}
#include <iostream>
#include <stack>

using namespace std;

int main() 
{
  int q, type, value;
  char operation;
  stack<int> S1, S2;
  stack<char> S3, S4;
    
  cin >> q;
  while(q--)
  {
    cin >> type;
    if(type == 1)
    {
      cin >> value;
      S1.push(value);
    }
    else if(type == 2)
    {
      S3.push('d');
    }
    else
    {
      S3.push('p');
    }
  }

  // Perform the actual operations.
  while(!S1.empty())
  {
    value = S1.top();
    S1.pop();
    S2.push(value);
  }

  while(!S3.empty())
  {
    value = S3.top();
    S3.pop();
    S4.push(value);
  }

  while(!S2.empty())
  {
    operation = S4.top();
    value = S2.top();
    S4.pop();

    if(operation == 'p')
    {
      // Print.
      cout << value << endl;
    }
    else
    {
      // Dequeue.
      S2.pop();
    }
  }

  return 0;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.