چیک کریں کہ کیا کسی قطار کو کسی دوسرے قطار میں اسٹیک کا استعمال کرکے ترتیب دیا جاسکتا ہے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون امریکن ایکسپریس میک
سائپٹوگرافی قطار چھانٹ اسٹیک

مسئلہ یہ بیان

مسئلہ "چیک کریں کہ کیا کسی قطار کو اسٹیک کا استعمال کرتے ہوئے کسی دوسری قطار میں ترتیب دیا جاسکتا ہے"۔ یہ بیان کرتا ہے کہ آپ کو ایک قطار دی گئی ہے جس میں این عناصر شامل ہیں ، قطار میں موجود عناصر نمبر 1 سے n کی ترتیب ہیں۔ چیک کریں کہ کیا یہ قطار کسی دوسرے قطار میں اسٹیک کی مدد سے ترتیب میں بڑھتی ہوئی ترتیب میں ترتیب دی جاسکتی ہے؟

مثال کے طور پر

queue = 8 -> 7 -> 5 -> 6 -> 4 -> 3 -> 2 -> 1
false

 

queue = 4 -> 1 -> 2 -> 3
true

چیک کرنے کے لئے الگورتھم چیک کریں کہ کیا اسٹیک کا استعمال کرتے ہوئے کسی قطار کو کسی اور قطار میں ترتیب دیا جاسکتا ہے

ابتدا میں ، دوسرا قطار اور اسٹیک خالی ہے اور عناصر پہلی قطار میں کچھ بے ترتیب ترتیب میں موجود ہیں۔
مقصد یہ ہے کہ ترتیب دیں اور عناصر کو اسٹیک کے استعمال کے ساتھ دوسری قطار میں رکھیں۔
نوٹ کریں کہ ہم قطار 2 میں عنصر داخل کر سکتے ہیں قطار 1 میں یا اسٹیک سے۔ یا تو قطار 1 کے سامنے کی قطار قطار 2 میں لگائی گئی ہے یا اسٹیک کے اوپری قطار میں قطار ہے۔
نیز ، ہمیں قطار میں پہلے عنصر کے بطور 1 ، دوسرے عنصر کی حیثیت سے 2 داخل کرنا ہے۔

1. Initialize a variable next as 1, this indicates that this variable should be inserted into queue 2.
2. If the front of the queue 1 or top of the stack is equals to next, remove the front or the top as required and move it to the queue 2, and increment next by 1.
3. Else if none of them is next, remove the front of queue 1 and push it to the stack and if the front of queue 1 is greater than top of stack, return false.
4. If all the elements are present in the queue 2, that is, both queue 1 and stack are empty, then it is possible to sort the queue, return true.

وضاحت

دوسری مثال پر غور کریں ،
قطار = 4 -> 1 -> 2 -> 3

ابتدائی طور پر،
کی 1 = 4 -> 1 -> 2 -> 3
q2 = کالعدم
اسٹیک = null

چیک کریں کہ کیا کسی قطار کو کسی دوسرے قطار میں اسٹیک کا استعمال کرکے ترتیب دیا جاسکتا ہے

ضابطے

جاوا کوڈ چیک کرنے کے لئے کہ کیا کسی قطار کو کسی دوسرے قطار میں اسٹیک کا استعمال کرکے ترتیب دیا جاسکتا ہے

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class CheckIfAQueueCanBeSortedIntoAnotherQueueUsingAStack {
    private static boolean checkIfPossible(Queue<Integer> q) {
        // Initialize next as 1
        int next = 1;

        Stack<Integer> st = new Stack<>();

        while (!q.isEmpty() || !st.isEmpty()) {
            // if front of queue is next, remove it and increment next
            if (!q.isEmpty() && q.peek() == next) {
                q.poll();
                next++;
            }
            // if top of stack is next, remove it and increment next
            else if (!st.isEmpty() && st.peek() == next) {
                st.pop();
                next++;
            } else {
                // if q is empty return false
                if (q.isEmpty()) {
                    return false;
                } 
                // remove front of queue and push it to top of stack
                else {
                    int front = q.poll();
                    if (st.isEmpty()) {
                        st.push(front);
                    } else {
                        // if front of queue is greater than top of stack, return false
                        if (front > st.peek()) {
                            return false;
                        } else {
                            st.push(front);
                        }
                    }
                }
            }
        }

        // all the elements can be sorted, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(8);
        q1.add(7);
        q1.add(5);
        q1.add(6);
        q1.add(4);
        q1.add(3);
        q1.add(2);
        q1.add(1);

        System.out.println(checkIfPossible(q1));

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(4);
        q2.add(1);
        q2.add(2);
        q2.add(3);

        System.out.println(checkIfPossible(q2));
    }
}
false
true

سی ++ کوڈ چیک کرنے کے لئے کہ کسی قطار کو کسی دوسرے قطار میں اسٹیک کا استعمال کرکے ترتیب دیا جاسکتا ہے

#include <bits/stdc++.h>
using namespace std;

bool checkIfPossible(queue<int> &q) {
    stack<int> st;
    
    // Initialize a variable next as 1
    int next = 1;
    
    while (!q.empty() || !st.empty()) {
        // if front of queue is next, remove it and increment next
        if (!q.empty() && q.front() == next) {
            q.pop();
            next++;
        }
        // if top of stack is next, remove it and increment next
        else if (!st.empty() && st.top() == next) {
            st.pop();
            next++;
        } else {
            // if q is empty return false
            if (q.empty()) {
                return false;
            } 
            // remove front of queue and push it to top of stack
            else {
                int front = q.front();
                q.pop();
                if (st.empty()) {
                    st.push(front);
                } else {
                    // if front of queue is greater than top of stack, return false
                    if (front > st.top()) {
                        return false;
                    } else {
                        st.push(front);
                    }
                }
            }
        }
    }
    
    
    return true;
}

int main() {
  // Example 1
    queue<int> q1;
    q1.push(8);
    q1.push(7);
    q1.push(5);
    q1.push(6);
    q1.push(4);
    q1.push(3);
    q1.push(2);
    q1.push(1);

    if (checkIfPossible(q1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    queue<int> q2;
    q2.push(4);
    q2.push(1);
    q2.push(2);
    q2.push(3);

    if (checkIfPossible(q2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  
  return 0;
}
false
true

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، جیسا کہ ہم پورے ان پٹ سے گزرتے ہیں۔ الگورتھم خطیر وقت کی پیچیدگی لیتا ہے۔

خلائی پیچیدگی

O (N) ، جیسا کہ ہم نے عناصر کو قطار یا اسٹیک میں محفوظ کرلیا ہے۔ الگورتھم لکیری جگہ لیتا ہے۔