ลบองค์ประกอบตรงกลางของสแต็ก


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน
Recursion กอง

คำชี้แจงปัญหา

ให้โครงสร้างข้อมูล (สแต็ก) เขียนโปรแกรมเพื่อลบองค์ประกอบตรงกลางของสแต็กที่กำหนดโดยใช้ฟังก์ชันพื้นฐานของสแต็ก -

  • push () - เพื่อแทรกองค์ประกอบในสแต็ก
  • pop () - เพื่อลบ / ลบองค์ประกอบด้านบนจากสแต็ก
  • ว่าง () - เพื่อตรวจสอบว่าขนาดของสแต็กมากกว่า 0 หรือไม่

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

ลบองค์ประกอบตรงกลางของสแต็ก

ตัวอย่าง

1 2 3 4 5
1 2 4 5
10 20 30 40 50 60
10 20 40 50 60

ขั้นตอนวิธี

  1. เริ่มต้นไฟล์ กอง โครงสร้างข้อมูลและผลักดันองค์ประกอบในนั้น
  2. สร้างฟังก์ชัน deleteMiddle ที่ยอมรับสแต็กขนาดและตัวแปรเพื่อแสดงดัชนีปัจจุบันเนื่องจากเป็นพารามิเตอร์ ตั้งค่าเริ่มต้นของตัวแปรดัชนีปัจจุบันเป็น 0
  3. ตรวจสอบว่าสแต็กว่างเปล่าหรือตัวแปรดัชนีปัจจุบันเท่ากับขนาดของสแต็กหรือไม่ให้ส่งคืน
  4. สร้างตัวแปร x และเก็บด้านบนของสแต็กไว้ในนั้น ลบ / ลบองค์ประกอบที่ด้านบนสุดของสแต็ก
  5. ทำการเรียกแบบเรียกซ้ำไปยังฟังก์ชันด้วยตัวเองขนาดของสแต็กและค่าของตัวแปรดัชนีปัจจุบัน + 1 เป็นพารามิเตอร์
  6. ตรวจสอบว่าค่าของตัวแปรดัชนีปัจจุบันไม่เท่ากับครึ่งหนึ่งของขนาดของสแต็กหรือไม่เช่นหากค่าของตัวแปรดัชนีปัจจุบันไม่เท่ากับดัชนีกลางของสแต็กให้ดันตัวแปร x กลับในสแตก
  7. หลังจากนั้นให้สำรวจในขณะที่ขนาดของสแต็กไม่เท่ากับ 0 สร้างตัวแปร p และเก็บส่วนบนสุดของสแต็กไว้ด้านบนของสแต็กและพิมพ์ตัวแปร p สำหรับการทำซ้ำทั้งหมด

สิ่งนี้ได้ผลเพราะเราใช้ความช่วยเหลือของการเรียกซ้ำเพื่อให้ด้านบนสุดของสแต็กที่เราเก็บไว้ในตัวแปร x เพื่อเก็บไว้ เรายังคงลบองค์ประกอบออกจากสแต็กเดิมและเก็บไว้ในตัวแปร ซึ่งที่นี่ทำหน้าที่เป็นสแต็กชั่วคราว และเราใส่องค์ประกอบทั้งหมดเข้าไปในสแต็กเดิมอีกครั้งยกเว้นองค์ประกอบที่ค่าปัจจุบัน = n / 2

รหัส

โปรแกรม C ++ เพื่อลบองค์ประกอบกลางของสแต็ก

#include<iostream>
#include<stack> 
using namespace std; 

void deleteMiddle(stack<char> &s, int n, int current=0){ 
    if(s.empty() || current == n){ 
        return; 
    }
    int x = s.top(); 
    s.pop();
    
    deleteMiddle(s, n, current+1); 
    
    if(current != n/2){ 
        s.push(x); 
    }
}

int main(){ 
    stack<char> st; 
    
    st.push('5'); 
    st.push('4'); 
    st.push('3'); 
    st.push('2'); 
    st.push('1'); 
    
    deleteMiddle(st, st.size()); 
    
    while(!st.empty()){ 
        char p=st.top(); 
        st.pop(); 
        cout << p << " "; 
    } 
    
    return 0; 
}
1 2 4 5

โปรแกรม Java เพื่อลบองค์ประกอบกลางของสแต็ก

import java.io.*; 
import java.util.*; 
  
class delMiddle{ 
  
    static void deleteMiddle(Stack<Character> st, int n, int curr){ 
          
        if(st.empty() || curr == n){ 
            return; 
        }
          
        char x = st.pop(); 
          
        deleteMiddle(st, n, curr+1); 
          
        if(curr != n/2){ 
            st.push(x); 
        }
    } 
      
    public static void main(String args[]){
        
        Stack<Character> st = new Stack<Character>(); 
      
        st.push('5'); 
        st.push('4'); 
        st.push('3'); 
        st.push('2'); 
        st.push('1'); 
        
        deleteMiddle(st, st.size(), 0); 
      
        while(!st.empty()){ 
            char p=st.pop(); 
            System.out.print(p + " "); 
        } 
    } 
}
1 2 4 5

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน) โดยที่ n คือจำนวนองค์ประกอบในสแต็ก เนื่องจากเราได้ลบองค์ประกอบทั้งหมดออกจากสแต็กแล้วใส่เข้าไปใหม่ในสแต็ก การแทรกและการนำองค์ประกอบออกจากสแต็กใช้เวลา O (1) ดังนั้นความซับซ้อนของเวลาสำหรับอัลกอริทึมจึงเป็นแบบเชิงเส้น

ความซับซ้อนของอวกาศ

บน) เนื่องจากเราใช้การเรียกซ้ำซึ่งจะใช้พื้นที่ในการจัดเก็บองค์ประกอบที่ถูกลบออก