Проверите да ли су елементи стека узастопно узастопно


Ниво тешкоће Лако
Често питани у Делхивери Фацтсет Фоуркитес
Стацк

Изјава о проблему

Проблем „Провери да ли су елементи стека узастопно узастопни“ наводи да сте добили а стек структура података о цео број тип. Направите функцију да бисте проверили да ли су сви дати елементи узастопно узастопни (било у порасту или умањењу) или не. Ако је број елемената даних у стеку паран, проверите да ли сви парови остављају елемент на врху датог стека. Такође, задржите елементе датог стека током програма и одштампајте их са резултатом.

Проверите да ли су елементи стека узастопно узастопно

Пример

s = [4, 5, -2, -3, 11, 10, 5, 6, 20]
Yes

Објашњење: Садржај слога (од врха) након позива функције [20 6 5 10 11 -3 -2 5 4]. Број елемената у гомили је непаран. Тако се 20 не упарује ни са једним елементом. Али остали елементи су упарени и узастопно су у пару.

s = [4, 6, 6, 7, 4, 3]
No

Објашњење: Садржај слога (одозго) након позива функције [3 4 7 6 6 4]. А пошто 4 и 6 имају разлику од 2, нису узастопни. Тако је резултат бр.

Алгоритам за проверу да ли су елементи стека узастопно узастопни

1. Create a stack data structure of the integer type and insert/push the elements in it.
2. Create another auxiliary stack data structure of the integer type.
3. Traverse while the original stack is not empty and push the element at top of  the auxiliary stack and pop the element from the top of the original stack.
4. Create a variable result of the boolean type and set its value as true.
5. Traverse through the auxiliary stack and pop the top 2 elements in the auxiliary stack and store them in 2 integer variables.
6. Check if the absolute difference of both the integer variables is not equal to 1, update the boolean variable result as false. Push / insert both the integer variables in the original stack.
7. Check if the size of the auxiliary stack is equal to 1, Push/insert the element at the top of the auxiliary stack in the original stack.
8. Return the boolean variable result.
9. Check if the returned value is equal to true, print "Yes" else print "No".
10. Print the original stack.

У овом проблему добијамо почетни оригинални стог који треба проверити. Дакле, креирамо помоћни стек који је направљен само зато што не желимо да изгубимо оригинални стек. Да нисмо желели да сачувамо почетни стог и можемо да модификујемо почетни стог, могли бисмо једноставно извадити елементе из оригиналног стога. Дакле, помоћни стек служи као копија стека. Сада када имамо помоћни стог, можемо уклонити 2 елемента са врха, а затим проверимо повезаност.

код

Ц ++ програм за проверу да ли су елементи стека узастопно узастопни

#include <bits/stdc++.h> 
using namespace std; 
  
bool isConsecutive(stack<int> s){ 
    stack<int> aux; 
    
    while(!s.empty()){ 
        aux.push(s.top()); 
        s.pop(); 
    } 
  
    bool result = true; 
    
    while(aux.empty() > 1){ 
        int x = aux.top(); 
        aux.pop(); 
        int y = aux.top(); 
        aux.pop(); 
        
        if(abs(x - y) != 1){ 
            result = false; 
        }
  
        s.push(x); 
        s.push(y); 
    } 
  
    if(aux.size() == 1){ 
        s.push(aux.top());
    }
  
    return result; 
} 
  
int main(){ 
    stack<int> s;
    
    s.push(4); 
    s.push(5); 
    s.push(-2); 
    s.push(-3); 
    s.push(11); 
    s.push(10); 
    s.push(5); 
    s.push(6); 
    s.push(20); 
  
    if(isConsecutive(s)){ 
        cout << "Yes" << endl; 
    }
    
    else{
        cout << "No" << endl;
    }
  
    cout << "Stack content (from top)"
          " after function call\n"; 
    
    while(s.empty() == false){ 
       cout << s.top() << " "; 
       s.pop(); 
    } 
  
    return 0; 
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

Јава програм за проверу да ли су елементи стека узастопно узастопни

import java.util.*; 

class CheckPair{ 
    
    static boolean isConsecutive(Stack<Integer> s){  
        Stack<Integer> aux = new Stack<Integer> ();  
        
        while(!s.isEmpty()){  
            aux.push(s.peek());  
            s.pop();  
        }  
      
        boolean result = true;  
        
        while(aux.size() > 1){  
            int x = aux.peek();  
            aux.pop();  
            int y = aux.peek();  
            aux.pop();  
            
            if(Math.abs(x - y) != 1){  
                result = false;  
            }
      
            s.push(x);  
            s.push(y);  
        }  
      
        if(aux.size() == 1){  
            s.push(aux.peek());
        }
      
        return result;  
    }  
      
    public static void main(String[] args){  
        Stack<Integer> s = new Stack<Integer> ();
        
        s.push(4);  
        s.push(5);  
        s.push(-2);  
        s.push(-3);  
        s.push(11);  
        s.push(10);  
        s.push(5);  
        s.push(6);  
        s.push(20);  
      
        if(isConsecutive(s)){  
            System.out.println("Yes");
        }
        
        else{
            System.out.println("No");  
        }
      
        System.out.println("Stack content (from top) after function call");  
        
        while(s.isEmpty() == false){  
            System.out.print(s.peek() + " ");  
            s.pop();  
        }  
      
    }  
}
Yes
Stack content (from top) after function call
20 6 5 10 11 -3 -2 5 4

Анализа сложености

Сложеност времена

НА), где је Н број елемената у стеку.

Сложеност простора

НА), користили смо стог за складиштење Н елемената. Тако се постиже линеарна сложеност простора.