C++でスタックのポップ操作回数を数えて配列の各要素を取得する方法

数値の配列とスタックが与えられます。配列のすべての要素はスタック内に格納されており、各配列要素を取り出すために必要なポップ操作の回数を求めるのが目的です。

スタックには要素が降順で格納されており、最下部の要素が最大値、最上部（トップ）の要素が最小値となります。

入力例

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

出力

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

説明

配列を先頭のインデックスから順に走査します。2 を取得するにはスタックを 3 回ポップする必要があるため、arr[0] は 3 になります。このとき最初の 2 回のポップで 7 と 6 も一緒に取り出されます。次に 1 を取得するには 1 回ポップするだけでよいので、arr[1] は 1 です。6 と 7 はすでにポップ済みのため、arr[2] = arr[3] = 0 となります。

別の入力例

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

出力

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

説明

配列を先頭から順に走査します。最初の 1 を取得するにはスタックを 3 回ポップする必要があり、arr[0] は 3 です。このとき 3 と 2 も同時に取り出されます。次の 2 はすでにポップ済みなので arr[1] は 0。続く 1 を取得するにはさらに 1 回ポップが必要なため arr[2] は 1、最後の 3 はすでに取り出し済みなので arr[3] は 0 となります。

アルゴリズムの考え方

このアプローチでは、unordered_map<int, bool> 型の変数 um を使い、ある要素がすでにポップ済みかどうかを判定します。要素をポップするたびに um に登録し、対象の要素がすでに登録済みならポップ回数は 0 として扱います。未登録の場合は、目的の要素が見つかるまでポップを繰り返してカウントを増やしていきます。

• 整数型の配列 arr[] を用意します。
• 要素を格納するための stack<int> 型の stck を用意します。
• 要素を降順でスタックにプッシュします。
• 関数 pop_operations(stack<int>& stck, int arr[], int elements) は、配列の各要素を取得するために必要なポップ操作の回数を計算して出力します。
• 初期カウントを 0 に設定します。
• ポップ操作中に出現した一意な数値を記録する unordered_map<int, bool> 型の um を用意します。
• for ループで配列を先頭から走査します。
• temp = arr[i] として現在の対象要素を取得します。
• temp がすでに um に存在する（＝ポップ済みの）場合は、ポップ操作不要として 0 を出力します。
• そうでない場合は、temp が見つかるまでスタックをポップし続け、ポップした各要素を um に true として記録しながらカウントを増やします。
• while ループを抜けた時点でカウントを出力します。
• これにより、配列の各要素に対応するポップ操作の回数が出力されます。

コード例

#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;
}

出力

上記のコードを実行すると、次の出力が得られます。

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