چيڪ ڪريو ته قطار کي قطار ذريعي ٻي قطار ۾ ترتيب ڏئي سگهجي ٿو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon آمريڪي ايڪسپريس ايم
جغرافيه پنگتي حيثيت رکي ٿو ترتيب ڏيڻ چتي

مسئلي جو بيان

مسئلو ”چيڪ ڪريو ته قطار کي قطار ذريعي ٻي قطار ۾ ترتيب ڏئي سگهجي ٿو“ ٻڌائي ٿو ته توهان کي قطار ۾ هڪ عنصر ڏنا ويندا آهن ، قطار ۾ موجود عناصر عدد 1 کان ن تائين اجازت ڏنل آهن. چيڪ ڪريو ته ڇا هي قطار ترتيب واري ترتيب سان ڪنهن ٻئي قطار ۾ ترتيب ڏيڻ سان ترتيب ڏئي سگهجي ٿي.

مثال

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

 

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

چيڪ ڪرڻ لاءِ الورگيتم ڇا هڪ قطار کي قطار ذريعي هڪ ٻئي قطار ۾ ترتيب ڏئي سگهجي ٿو

شروعات ۾ ، ٻيو پنگتي حيثيت رکي ٿو ۽ اسٽيڪ خالي آهن ۽ عنصر پهرين قطار ۾ ڪجهه بي ترتيب ترتيب ۾ موجود آهن.
مقصد مقصد آهي ترتيب ڏيو ۽ عناصر کي اسٽيڪ جي استعمال سان ٻئي قطار ۾ رک.
ياد رکو ته اسان قطار 2 ۾ يا ته قطار 1 مان هڪ عنصر داخل ڪري سگهون ٿا يا قطار. اھو آھي ته يا ته قطار 1 جو قطار قطار 2 آھي يا اسٽيڪ جي چوٽي بيھي آھي.
انهي سان گڏ ، اسان کي 1 کي قطار کي پهريون عنصر 2 ، 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

شروعات ۾،
q1 = 4 -> 1 -> 2 -> 3
q2 = نيل
اسٽيڪ = نڪ

چيڪ ڪريو ته قطار کي قطار ذريعي ٻي قطار ۾ ترتيب ڏئي سگهجي ٿو

ڪوڊ

جاوا ڪوڊ اهو چيڪ ڪرڻ لاءِ ته قطار ذريعي قطار کي ٻي قطار ۾ ترتيب ڏئي سگهجي ٿو

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، جيئن اسان سموري ان پٽ ذريعي چڙهائي ڪئي. الگورٿيم ڏڪيل وقت جي پيچيدگي وٺندو آهي.

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

اي (اين) ، جئين اسان عناصر کي قطار يا اسٽوري ۾ محفوظ ڪيو آهي. الگورٿيم لڪير واري جاءِ وٺندو آهي.