Đếm số phép pop trên stack để lấy từng phần tử của mảng trong C++

Cho một mảng các số và một stack. Tất cả các phần tử của mảng đều có mặt bên trong stack. Mục tiêu là tìm số lượng phép pop cần thiết để lấy từng phần tử của mảng.

Stack được điền theo thứ tự giảm dần, phần tử đầu tiên là lớn nhất và phần tử đỉnh là nhỏ nhất.

Ví dụ

Đầu vào

Stack [ 7,6,2,1 ] mảng: 2,1,6,7

Đầu ra

Số phép pop trên stack để lấy từng phần tử của mảng là: 3 1 0 0

Giải thích

Duyệt mảng từ chỉ số 0, để lấy 2 ta sẽ pop stack 3 lần. Vậy arr[0] là 3. Hai lần pop đầu sẽ cho 7 và 6. Để lấy 1 ta sẽ pop stack 1 lần nữa. Vậy arr[1] là 1. Đối với 6 và 7 vì đã được pop rồi, nên arr[2]=arr[3]=0.

Đầu vào

Stack [ 3,2,1,1 ] mảng: 1,2,1,3

Đầu ra

Số phép pop trên stack để lấy từng phần tử của mảng là: 3 0 1 0

Giải thích

Duyệt mảng từ chỉ số 0, để lấy 1 ta sẽ pop stack 3 lần. Vậy arr[0] là 3. Hai lần pop đầu sẽ cho 3 và 2.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ sử dụng một unordered_map<int, bool> um để kiểm tra xem phần tử đã được pop hay chưa. Pop phần tử và thêm nó vào um. Nếu nó xuất hiện lại thì đặt số lần pop là 0. Nếu không thì tăng biến đếm cho đến khi tìm thấy nó.

• Nhận mảng nguyên arr[].
• Nhận stack<int> stck để lưu trữ các phần tử.
• Đẩy các phần tử vào theo thứ tự giảm dần.
• Hàm pop_operations(stack<int>& stck, int arr[], int elements) trả về số phép pop trên stack để lấy từng phần tử của mảng.
• Khởi tạo biến đếm ban đầu là 0.
• Tạo unordered_map<int, bool> um để lưu trữ các số duy nhất gặp được khi thực hiện pop trên stack.
• Duyệt mảng bằng vòng lặp for.
• Lấy temp = arr[i].
• Nếu temp không có trong um. In 0 phép pop cần thiết để lấy nó.
• Ngược lại trong khi temp không được tìm thấy, thực hiện pop trên stack và đặt mỗi phần tử được pop trong um là true và tăng biến đếm.
• Cuối cùng của vòng while, in biến đếm.
• Theo cách này chúng ta sẽ in số phép pop cho từng phần tử của mảng.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 

void pop_operations(stack<int>& stck, int arr[], int elements) {
    int count = 0;
    unordered_map<int, bool> um;
    cout << "Số phép pop trên stack để lấy từng phần tử của mảng là: ";
    
    for (int i = 0; i < elements; ++i) {
        int temp = arr[i];
        
        if (um.find(temp) != um.end()) {
            cout << "0 ";
        } else {
            count = 0;
            while (stck.top() != temp) {
                um[stck.top()] = true;
                stck.pop();
                count++;
            }
            stck.pop();
            count++;
            cout << count << " ";
        }
    }
}

int main() {
    int elements = 4;
    int arr[] = { 2, 1, 6, 7 };
    stack<int> stck;
    stck.push(1);
    stck.push(2);
    stck.push(6);
    stck.push(7);
    pop_operations(stck, arr, elements);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số phép pop trên stack để lấy từng phần tử của mảng là: 3 1 0 0