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[]를 가져옵니다.
요소를 저장하기 위해 stack stck를 가져옵니다.
내림차순으로 요소를 푸시합니다.
함수 pop_operations(stack&stck, int arr[], int elements)는 배열의 각 요소를 가져오기 위해 스택에서 팝 작업의 수를 반환합니다.
초기 카운트를 0으로 합니다.
스택에서 팝 작업을 수행하는 동안 발생한 고유 번호를 저장하려면 unordered_map um을 사용합니다.
for 루프를 사용하여 배열을 탐색합니다.
temp=arr[i]을(를) 가져옵니다.
온도가 음이 아닌 경우. 그것을 얻는 데 필요한 0개의 팝 작업을 인쇄하십시오.
그렇지 않으면 temp를 찾을 수 없는 동안 스택에서 팝을 수행하고 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