Cho một mảng số và một ngăn xếp. Tất cả các phần tử của mảng đều có bên trong ngăn xếp Mục tiêu là tìm số lượng các phép toán bật lên cần thiết để nhận các phần tử mảng riêng lẻ.
Ngăn xếp được lấp đầy theo thứ tự giảm dần, phần tử đầu tiên là cao nhất và phần tử trên cùng là thấp nhất.
Ví dụ
Đầu vào
Stack [ 7,6,2,1 ] array : 2,1,6,7
Đầu ra
Count of number of pop operations on stack to get each element of the array are: 3 1 0 0
Giải thích
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.
Đầu vào
Stack [ 3,2,1,1 ] array : 1,2,1,3
Đầu ra
Count of number of pop operations on stack to get each element of the array are: 3 0 1 0
Giải thích
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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng ta sẽ sử dụng một hàm chưa có thứ tự_map
-
Lấy một mảng số nguyên arr [].
-
Lấy một ngăn xếp
stck để lưu trữ các phần tử trong đó. -
Đẩy các phần tử trong đó theo thứ tự giảm dần.
-
Hàm pop_operations (stack
&stck, int arr [], int element) trả về số lượng các phép toán pop trên ngăn xếp để lấy từng phần tử của mảng. -
Lấy số lượng ban đầu là 0.
-
Hãy dùng unardered_map
-
Traverse mảng sử dụng vòng lặp for.
-
Lấy temp =arr [i].
-
Nếu nhiệt độ không ở trong um. In 0 thao tác pop cần thiết để lấy nó.
-
Nếu không, trong khi không tìm thấy tạm thời, hãy thực hiện bật trên ngăn xếp và đặt từng phần tử xuất hiện trong ô là đúng và số gia tăng.
-
Vào cuối thời gian, hãy đếm số bản in.
-
Bằng cách này, chúng tôi sẽ in ra số lượng các phép toán pop cho mỗi phần tử của mảng.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of pop operations on stack to get each element of the array are: 3 1 0 0