数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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<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
更新于： 2021年1月5日
575 次查看
广告