ตรวจสอบว่าอาร์เรย์สามารถจัดเรียงสแต็กได้ใน C ++ . หรือไม่

สมมติว่าเรามีจำนวนอาร์เรย์ขององค์ประกอบเฉพาะตั้งแต่ 1 ถึง n เราต้องตรวจสอบก่อนว่า stack-sortable หรือไม่ อาร์เรย์สามารถจัดเรียงสแต็กได้เมื่อจัดเก็บในอาร์เรย์อื่นโดยใช้สแต็กชั่วคราว

เพื่อแก้ปัญหานี้ เราสามารถใช้การดำเนินการใดๆ เหล่านี้กับอาร์เรย์ -

• ลบองค์ประกอบเริ่มต้นของอาร์เรย์และพุชรายการนั้นลงในสแต็ก

• ลบองค์ประกอบบนสุดของสแต็กและแทรกไว้ที่ส่วนท้ายของอาร์เรย์ที่สอง

ตอนนี้ถ้าองค์ประกอบทั้งหมดของอาร์เรย์ที่กำหนดถูกถ่ายโอนไปยังอาร์เรย์ที่สองโดยการดำเนินการเหล่านี้ ดังนั้นอาร์เรย์ที่สองจึงถูกจัดเรียงตามลำดับที่ไม่ลดลง อาร์เรย์ที่ระบุจะสามารถจัดเรียงแบบสแต็กได้

ดังนั้นหากอินพุตเป็น nums =[8, 6, 5, 3, 1] เอาต์พุตจะเป็น True เนื่องจากเราสามารถหมุนสองครั้งตามทิศทางตามเข็มนาฬิกา มันก็จะเรียงลำดับเช่น [1, 3, 4, 5, 6, 8]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งสแต็ก stk
• สุดท้าย :=0
• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • ถ้า stk ไม่ว่างเปล่า ดังนั้น −
    • top :=องค์ประกอบด้านบนของ stk
    • ในขณะที่ด้านบนเหมือนกับ (สุดท้าย + 1) ให้ทำ −
      • สุดท้าย :=สุดท้าย + 1
      • ป๊อปจาก stk
      • ถ้า stk ว่างเปล่า ดังนั้น:
        • ออกมาจากวงจร
      • top :=องค์ประกอบด้านบนของ stk
    • ถ้า stk ว่างเปล่า ดังนั้น:
      • ดัน v[i] เข้าสู่ stk
    • มิฉะนั้น
      • top :=องค์ประกอบด้านบนของ stk
      • ถ้า v[i] <ด้านบน แล้ว:
        • ดัน v[i] เข้าสู่ stk
      • มิฉะนั้น
        • คืนค่าเท็จ
  • มิฉะนั้น
    • ดัน v[i] เข้าสู่ stk
• คืนค่าจริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &v) {
   stack<int> stk;
   int last = 0;
   for (int i = 0; i < v.size(); i++) {
      if (!stk.empty()){
         int top = stk.top();
         while (top == last + 1) {
            last = last + 1;
            stk.pop();
            if (stk.empty()){
               break;
            } top = stk.top();
         }
         if (stk.empty()) {
            stk.push(v[i]);
         }else{
            top = stk.top();
            if (v[i] < top){
               stk.push(v[i]);
            }else{
               return false;
            }
         }
      }else{
         stk.push(v[i]);
      }
   } return true;
}
main(){
   vector<int>
   v = {8, 6, 5, 3, 1};
   cout << solve(v);
}

อินพุต

{8, 6, 5, 3, 1}

ผลลัพธ์

1