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


Ниво на трудност Лесно
Често задавани в Делхейвъри FactSet Fourkites
Стек

Декларация за проблема

Проблемът „Проверете дали елементите на стека са двойно последователни“ посочва, че сте получили a купчина структура на данните на цяло число Тип. Създайте функция, за да проверите дали всички дадени елементи са последователни по двойки (в нарастващ или намаляващ ред) или не. Ако броят на елементите, дадени в стека, е четен, проверете дали всички двойки оставят елемента в горната част на дадения стек. Също така запазете елементите на дадения стек по време на програмата и ги отпечатайте с резултата.

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

Пример

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, те не са последователни. По този начин резултатът е No.

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

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 елемента отгоре и след това да проверим за свързаност.

код

Програма C ++ за проверка дали елементите на стека са последователни по двойки

#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

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

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

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

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

НА), където N е броят на елементите в стека.

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

НА), използвахме стек за съхраняване на N елемента. Така се постига линейна сложност на пространството.