資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告