Проверите да ли се ред може сортирати у други ред помоћу стека


Ниво тешкоће Средњи
Често питани у амазонка америцан екпресс МАК
Циптографија Ред сортирање Стацк

Изјава о проблему

Проблем „Провери да ли се ред може сортирати у други ред помоћу стека“ наводи да сте добили ред који садржи н елемената, елементи у реду су пермутација бројева од 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

На почетку,
к1 = 4 -> 1 -> 2 -> 3
к2 = нула
стацк = нулл

Проверите да ли се ред може сортирати у други ред помоћу стека

код

Јава код за проверу да ли се ред може сортирати у други ред помоћу стека

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

Анализа сложености

Сложеност времена

НА), док смо пролазили кроз цео улаз. Алгоритам узима линеарну временску сложеност.

Сложеност простора

НА), пошто смо елементе ускладиштили у ред или стек. Алгоритам узима линеарни простор.