检查是否可以使用堆栈将一个队列分类到另一个队列中


难度级别 中等
经常问 亚马逊 美国运通卡 空气质量
密码学 队列 排序

问题陈述

问题“检查一个队列是否可以使用堆栈分类到另一个队列中”指出给您一个包含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

最初,
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

复杂度分析

时间复杂度

上), 当我们遍历整个输入时。 该算法采用线性时间复杂度。

空间复杂度

上), 因为我们已经将元素存储到队列或堆栈中。 该算法占用线性空间。