تحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أمريكان إكسبريس MAQ
علم الحاسوب طابور فرز كومة

المشكلة بيان

توضح المشكلة "تحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس" أنه يتم منحك قائمة انتظار تحتوي على عناصر n ، والعناصر الموجودة في قائمة الانتظار هي تبديل للأرقام من 1 إلى n. تحقق مما إذا كان يمكن ترتيب قائمة الانتظار هذه بترتيب متزايد في أي قائمة انتظار أخرى بمساعدة مكدس.

مثال

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

 

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

خوارزمية للتحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس

في البداية ، الثانية طابور والمكدس فارغان والعناصر موجودة بترتيب عشوائي في قائمة الانتظار الأولى.
الهدف هو sort ووضع العناصر في قائمة الانتظار الثانية باستخدام مكدس.
لاحظ أنه يمكننا إدراج عنصر في قائمة الانتظار 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 = لا شيء
مكدس = فارغ

تحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس

رمز

كود Java للتحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس

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

كود C ++ للتحقق مما إذا كان يمكن فرز قائمة انتظار في قائمة انتظار أخرى باستخدام مكدس

#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) حيث قمنا بتخزين العناصر في قائمة انتظار أو مكدس. تأخذ الخوارزمية مساحة خطية.