C++ Coding Test Course, Creating Ascending Sequences with Stacks

Problem Description

You need to sort the numbers of a given sequence in ascending order using a stack. Every time a specific number comes in, you must examine the current state of the stack and, if possible, create an ascending sequence. If it is impossible, an appropriate message should be displayed.

Input

• The first line contains an integer N (1 ≤ N ≤ 100,000). (N is the number of integers in the sequence)
• The second line contains N integers, i.e., the sequence. (1 ≤ each integer in the sequence ≤ 1,000,000)

Output

• If the sequence can be made in ascending order, print ‘YES’.
• If the sequence cannot be made in ascending order, print ‘NO’.

Example Input

        5
        4 3 6 8 5
        

Example Output

        NO
        

Solution Process

To solve this problem, we need to effectively utilize the main properties of a stack. We will read the numbers from the left in order and push them into the stack, checking whether the top number of the stack matches the number we need to sort currently. Below is a step-by-step explanation of this process.

Step 1: Input Processing

First, we read the number of input numbers and receive the sequence accordingly. We plan to push this sequence into the stack in order.

Step 2: Sequence Manipulation Using Stack

Every time a number is input, we need to perform two tasks.

• Push the current number onto the stack.
• If the top number of the stack is the next number in our target ascending sequence, pop it from the stack and output it as a result.

Step 3: Handling Impossible Cases

If we processed all the input sequence but were unable to output the entire target sequence, print ‘NO’ and terminate the process.

Step 4: Code Implementation

Now, let’s implement this process in C++ code.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector sequence(N);
    for (int i = 0; i < N; i++) {
        cin >> sequence[i];
    }

    stack s;
    vector result;

    int next = 1; // The number to be sorted in ascending order
    for (int i = 0; i < N; i++) {
        s.push(sequence[i]); // Push the current number onto the stack.

        // Check if the top of the stack matches next.
        while (!s.empty() && s.top() == next) {
            result.push_back(s.top()); // Add the top element of the stack to the result.
            s.pop(); // Pop the top from the stack.
            next++; // Proceed to the next number.
        }
    }

    // Check if all numbers have been sorted.
    if (result.size() == N) {
        cout << "YES" << endl; // Successfully created an ascending sequence.
    } else {
        cout << "NO" << endl; // Failed.
    }

    return 0;
}
        

Conclusion

In this course, we learned how to sort given numbers in ascending order using a stack. By leveraging the characteristics of the stack, we could manipulate numbers in real-time and check if the conditions were satisfied. Understanding data structures is crucial in coding test problems, so I encourage you to build your skills through various problems in the future.

Further Progress

There are various problems that utilize stacks. Next time, we will tackle problems using queues or other data structures. Thank you for your interest!