นับจำนวนการ Pop จาก Stack เพื่อหาแต่ละสมาชิกในอาร์เรย์ด้วย C++

ได้รับอาร์เรย์ตัวเลขและสแต็ก สมาชิกทั้งหมดของอาร์เรย์อยู่ภายในสแต็ก เป้าหมายคือหาจำนวนครั้งของการ pop ที่ต้องทำเพื่อดึงสมาชิกแต่ละตัวของอาร์เรย์ออกมา สแต็กถูกเติมในลำดับลดลง สมาชิกแรกมีค่ามากที่สุด และตัวบนสุดมีค่าน้อยที่สุด

ตัวอย่าง

Input

Stack [ 7,6,2,1 ] array : 2,1,6,7

Output

Count of number of pop operations on stack to get each element of the array are: 3 1 0 0

Explanation

Traversing array from 0th index, To get 2 we will pop stack three times. So arr[0] is 3. First two pops will give 7 and 6 also. To get 1 we will pop stack once now. So arr[1] is 1. For 6 and 7 as these are already popped, so arr[2]=arr[3]=0.

Input

Stack [ 3,2,1,1 ] array : 1,2,1,3

Output

Count of number of pop operations on stack to get each element of the array are: 3 0 1 0

Explanation

Traversing array from 0th index, To get 1 we will pop stack three times. So arr[0] is 3. First two pops will give 3 and 2 also.

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้ unordered_map<int, bool> um เพื่อตรวจสอบว่าสมาชิกถูก pop ไปแล้วหรือยัง Pop สมาชิกแล้วเพิ่มเข้า um ถ้ามันมาใหม่ ให้ตั้งจำนวน pop เป็น 0 ถ้าไม่ได้ ให้เพิ่มจำนวนนับจนกว่าจะเจอ

• รับอาร์เรย์จำนวนเต็ม arr[]
• รับ stack<int> stck สำหรับเก็บสมาชิก
• Push สมาชิกเข้าไปในลำดับลดลง
• ฟังก์ชัน pop_operations(stack<int>& stck, int arr[], int elements) คืนค่าจำนวน pop operations
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• สร้าง unordered_map<int, bool> um เก็บตัวเลขที่เจอขณะ pop
• วนลูปผ่านอาร์เรย์
• เก็บ temp = arr[i]
• ถ้า temp ไม่อยู่ใน um พิมพ์ 0 pop operations
• มิฉะนั้น while temp ยังไม่เจอ ให้ pop จาก stack และตั้งค่าแต่ละตัวที่ pop ใน um เป็น true และเพิ่ม count
• เมื่อ while จบ พิมพ์ count
• ทำเช่นนี้สำหรับทุกสมาชิกในอาร์เรย์

ตัวอย่างโค้ด

#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 << "Count of number of pop operations on stack to get each element of the array are: ";
    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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of pop operations on stack to get each element of the array are: 3 1 0 0