چیک کریں کہ اسٹیک عناصر لگاتار جوڑا لگاتے ہیں یا نہیں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے دہلی حقیقت فورکائٹس
اسٹیک

مسئلہ یہ بیان

"چیک کریں کہ اسٹیک عناصر مسلسل جوڑا لگاتے ہیں" مسئلہ بیان کرتا ہے کہ آپ کو ایک ڈھیر لگانا کے اعداد و شمار کی ساخت عددی قسم۔ یہ معلوم کرنے کے لئے ایک فنکشن بنائیں کہ دیئے گئے تمام عناصر مسلسل جوڑا لگاتے ہیں (یا تو بڑھتے ہوئے یا کم ہوتے ہوئے ترتیب میں) یا نہیں۔ اگر اسٹیک میں دیئے گئے عناصر کی تعداد برابر ہے تو ، تمام جوڑے چیک کریں اور باقی عنصر کو دیئے گئے اسٹیک کے اوپری حصے پر چھوڑ دیں۔ اس کے علاوہ ، پروگرام کے دوران دیئے گئے اسٹیک کے عناصر کو برقرار رکھیں اور ان کو نتائج کے ساتھ پرنٹ کریں۔

چیک کریں کہ اسٹیک عناصر لگاتار جوڑا لگاتے ہیں یا نہیں

مثال کے طور پر

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

جاوا پروگرام یہ چیک کرنے کے ل if کہ اسٹیک عناصر مسلسل جوڑا لگاتے ہیں یا نہیں

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N)، جہاں اسٹیک میں عناصر کی تعداد N ہے۔

خلائی پیچیدگی

O (N)، ہم نے این عناصر کو ذخیرہ کرنے کے لئے اسٹیک استعمال کیا ہے۔ اس طرح ایک لکیری جگہ پیچیدگی حاصل کی جاتی ہے۔