შეამოწმეთ, შესაძლებელია თუ არა რიგის დახარისხება სხვა რიგში სტეკის გამოყენებით  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon American Express MAQ
ციპტოგრაფია Queue დახარისხება დასტის

პრობლემის განცხადება  

პრობლემა "შეამოწმეთ შესაძლებელია თუ არა რიგის დახარისხება სტეკის გამოყენებით სხვა რიგში" ნათქვამია, რომ თქვენ გეძლევათ რიგი, რომელიც შეიცავს n ელემენტს, რიგში მყოფი ელემენტები არის ნომრის 1-დან n- ის შეცვლა. შეამოწმეთ, შესაძლებელია თუ არა ამ რიგის განლაგება მწკრივის დახმარებით სხვა რიგში.

მაგალითი  

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

იხილეთ ასევე
BST– ის უპირატესობები ჰეშის მაგიდასთან შედარებით

თავდაპირველად,
q1 = 4 -> 1 -> 2 -> 3
q2 = ნული
დასტა = null

შეამოწმეთ, შესაძლებელია თუ არა რიგის დახარისხება სხვა რიგში სტეკის გამოყენებითPin

კოდი  

ჯავის კოდი იმისთვის, რომ შეამოწმოს, არის თუ არა რიგის დახარისხება სტრიქონის გამოყენებით სხვა რიგში

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), რადგან ელემენტები შევინახეთ რიგში ან სტეკში. ალგორითმი იღებს სწორხაზოვან ადგილს.