بررسی کنید که آیا عناصر پشته به صورت جفتی متوالی هستند


سطح دشواری ساده
اغلب در تحویل کالا واقعیت فورکایت
پشته

بیان مسأله

در مسئله "بررسی کنید که آیا عناصر پشته به صورت جفتی پشت سر هم قرار گرفته اند" بیان می کند که به شما 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 دارند ، متوالی نیستند. بنابراین نتیجه خیر است.

الگوریتم برای بررسی اینکه عناصر پشته به صورت جفتی متوالی هستند یا خیر

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

برنامه جاوا برای بررسی اینکه عناصر پشته به صورت جفتی متوالی هستند یا خیر

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 از پشته استفاده کرده ایم. بنابراین یک پیچیدگی فضای خطی حاصل می شود.