Праверце, ці можна сартаваць чаргу ў іншую чаргу, выкарыстоўваючы стэк


Узровень складанасці серада
Часта пытаюцца ў амазонка American Express MAQ
Цыптаграфія чаргу сартаванне Стэк

Пастаноўка праблемы

Праблема "Праверыць, ці можна сартаваць чаргу ў іншую чаргу з выкарыстаннем стэка", абвяшчае, што вы атрымаеце чаргу, якая змяшчае n элементаў, элементы ў чарзе з'яўляюцца перастаноўкай лікаў ад 1 да n. З дапамогай стэка праверце, ці можна размясціць гэтую чаргу ў павялічаным парадку ў любой іншай чарзе.

Прыклад

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

 

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

Алгарытм праверкі Праверце, ці можна сартаваць чаргу ў іншую чаргу з дапамогай стэка

Першапачаткова другі чаргу і стэк пустыя, і элементы прысутнічаюць у нейкім выпадковым парадку ў першай чарзе.
Мэта складаецца ў тым, каб сартаваць і змясціце элементы ў другую чаргу з выкарыстаннем стэка.
Звярніце ўвагу, што мы можам ўставіць элемент у чаргу 2 альбо з чаргі 1, альбо са стэка. Гэта значыць, альбо пярэдняя частка чаргі ў чарзе 1, альбо верхняя частка стэка.
Акрамя таго, мы павінны ўставіць 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), бо мы захавалі элементы ў чарзе ці стэку. Алгарытм займае лінейную прастору.