นับจำนวนการดำเนินการป๊อปบนสแต็กเพื่อรับแต่ละองค์ประกอบของอาร์เรย์ใน 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 เพื่อตรวจสอบว่าองค์ประกอบนั้นถูกเปิดแล้วหรือไม่ องค์ประกอบป๊อปและเพิ่มลงในอืม ถ้ามันมาอีก ให้ตั้ง popping count เป็น 0 ถ้าไม่ขึ้นก็นับจนกว่าเราจะได้มันมา

• ใช้อาร์เรย์จำนวนเต็ม arr[].

• นำ stack stck เพื่อจัดเก็บองค์ประกอบในนั้น

• ดันองค์ประกอบในลำดับที่ลดลง

• ฟังก์ชัน pop_operations(stack&stck, int arr[], องค์ประกอบ int) คืนค่าจำนวนการดำเนินการป๊อปบนสแต็กเพื่อรับแต่ละองค์ประกอบของอาร์เรย์

• นับเริ่มต้นเป็น 0

• ใช้ unordered_map um เพื่อจัดเก็บหมายเลขเฉพาะที่พบขณะดำเนินการป๊อปอัพบนสแต็ก

• Traverse array ใช้ for วนซ้ำ

• ใช้ temp=arr[i].

• ถ้าอุณหภูมิไม่อยู่ใน um ต้องพิมพ์ 0 ป๊อปอัพจึงจะโหลดได้

• มิฉะนั้นในขณะที่ไม่พบ temp ให้ดำเนินการป๊อปบนสแต็กและตั้งค่าแต่ละองค์ประกอบที่ปรากฏขึ้นใน um เป็นจริงและนับการเพิ่มขึ้น

• เมื่อสิ้นสุดระยะเวลาพิมพ์ ให้นับ

• ด้วยวิธีนี้ เราจะพิมพ์จำนวนการดำเนินการป๊อปสำหรับแต่ละองค์ประกอบของอาร์เรย์

ตัวอย่าง

#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