Стекийн дунд элементийг устгах


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
Сэтгэгдэл бичих Stack

Асуудлын мэдэгдэл

Өгөгдлийн бүтэц (стек) өгөгдсөн болно. Стекийн үндсэн функцийг ашиглан өгөгдсөн стекийн дунд элементийг устгах програм бич.

  • push () - элементийг стекд оруулах.
  • pop () - стекээс дээд элементийг устгах / устгах.
  • empty () - стекийн хэмжээ 0-ээс их эсэхийг шалгах.

Шинэчлэгдсэн стекийг өөрөөр хэлбэл элементийг дунд нь устгасны дараа стекийг хэвлэ. Бусад өгөгдлийн бүтцийг ашиглахыг зөвшөөрөхгүй.

Стекийн дунд элементийг устгах

Жишээ нь

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

Алгоритм

  1. Эхлүүлэх a стек өгөгдлийн бүтэц, түүний доторх элементүүдийг түлхэх.
  2. Функц үүсгэх устгах дунд стекийг хүлээн авдаг бөгөөд энэ нь одоогийн индексийг параметр болгон харуулах хэмжээ, хувьсагч юм. Одоогийн индекс хувьсагчийн анхдагч утгыг 0 гэж тохируулна уу.
  3. Стек хоосон эсвэл одоогийн индексийн хувьсагч нь стекийн хэмжээтэй тэнцүү байгаа эсэхийг шалгаад буцах.
  4. Хувьсагч үүсгэх x мөн стекийн дээд хэсгийг хадгална. Стекийн дээд хэсэгт байгаа элементийг устгах / устгах.
  5. Стек, стекийн хэмжээ, одоогийн индекс хувьсагчийн утга болох параметрийн хувьд функц руу рекурсив дуудлага хийнэ.
  6. Одоогийн индекс хувьсагчийн утга нь стекийн талтай тэнцүү биш эсэхийг шалгана уу, өөрөөр хэлбэл одоогийн индекс хувьсагчийн утга нь стекийн дунд индекстэй тэнцэхгүй бол x хувьсагчийг буцааж стек рүү түлхэж оруулна.
  7. Үүний дараа стекийн хэмжээ нь 0-тэй тэнцэхгүй байхад траамерлаарай, хувьсагч үүсгээд стекийн дээд хэсгийг хадгалаад стекийн дээд хэсгийг тавиад p хувьсагчийг бүх давталтад хэвлэ.

Бид хадгалсан стекийн дээд хэсгийг хувьсагчтай байлгахын тулд рекурсын тусламжийг авч байгаа тул энэ нь ажиллана x хадгалах. Бид анхны стекээс элементүүдийг авч, дотор нь хувьсагч хадгалсаар байдаг энд түр зуурын стекийн үүрэг гүйцэтгэдэг. Одоогийн утга = n / 2 байх элементээс бусад бүх элементүүдийг анхны стек рүү дахин оруулна.

код

С ++ стекийн дунд элементийг устгах програм

#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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) энд n нь стек дэх элементүүдийн тоо юм. Учир нь бид бүх элементүүдийг стекээс хасаад дараа нь стекд дахин оруулав. Элементийг стекээс оруулах, хасахад O (1) цаг хугацаа шаардагдана. Тиймээс алгоритмын цаг хугацааны нарийн төвөгтэй байдал нь шугаман байна.

Сансрын нарийн төвөгтэй байдал

O (N) Учир нь бид устгасан элементүүдийг хадгалах зайг ашиглах рекурсийг ашиглаж байна.