スタック上のポップ操作の数をカウントして、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

説明

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.

入力

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

説明

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.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 umを使用して、要素がすでにポップされているかどうかを確認します。要素をポップして、umに追加します。再び発生する場合は、ポップカウントを0に設定します。そうでない場合は、取得するまでカウントをインクリメントします。

• 整数配列arr[]を取ります。

• スタックstckを使用して、要素を格納します。

• その中の要素を降順で押します。

• 関数pop_operations（stack ＆stck、int arr []、int elements）は、配列の各要素を取得するためのスタック上のポップ操作の数を返します。

• 初期カウントを0とします。

• unordered_map umを使用して、スタックでポップ操作を実行しているときに検出された一意の数値を格納します。

• forループを使用して配列をトラバースします。

• temp =arr[i]を取ります。

• 温度がumにない場合。取得するために必要な0回のポップ操作を出力します。

• それ以外の場合、tempが見つからないときに、スタックでpopを実行し、umでポップされた各要素をtrueとして設定し、カウントをインクリメントします。

• しばらくすると、カウントを印刷します。

• このようにして、配列の各要素のポップ操作の数を出力します。

例

#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