Видалити середній елемент стека


Рівень складності Легко
Часто запитують у Амазонка
Рекурсія Стек

Постановка проблеми

Дана структура даних (стек). Напишіть програму для видалення середнього елемента даного стека, використовуючи основні функції стека -

  • 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. Створіть функцію 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

Аналіз складності

Складність часу

O (N) де n - кількість елементів у стеку. Оскільки ми вилучили всі елементи зі стеку, а потім знову вставили їх у стек. Вставка та вилучення елемента зі стопки займає час O (1). Таким чином, часова складність алгоритму є лінійною.

Складність простору

O (N) тому що ми використовуємо рекурсію, яка використовуватиме простір для зберігання видалених елементів.