ٻيهر استعمال ڪندي اسٽيڪ کي ترتيب ڏيو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon Goldman سيچ IBM ڪليزا ياهو
ٻيھر چتي

مسئلي جو بيان

مسئلو "ترتيب ڏيڻ سان اسٽيڪ کي ترتيب ڏيو" ۾ بيان ڪيو ويو آهي ته توهان کي هڪ ڏني وئي آهي اسٽيڪ ڊيٽا جو structureانچو. جي حساب سان انهي جو عنصر ترويج استعمال ڪندي. صرف اسٽيڪ جا هيٺيان فهرست ڏنل افعال استعمال ٿي سگھن ٿا.

  • ڌڪ (عنصر) - عنصر کي اسٽيڪ ۾ داخل ڪرڻ لاءِ.
  • پاپ () پاپ () - ڏنل اسٽيڪ جي چوٽي تي عنصر کي ختم ڪرڻ / ختم ڪرڻ.
  • isEmpty () - چيڪ ڪرڻ لاءِ آيا ته اسٽيڪ ۾ ڪو عنصر آهي يا نه.
  • مٿي () - ڏٺو ويو / ڏسڻ واري اسٽيڪ جي چوٽي تي عنصر.

ٻيهر استعمال ڪندي اسٽيڪ کي ترتيب ڏيو

مثال

9 4 2 -1 6 20
20 9 6 4 2 -1

وضاحت: اسٽوري کي ترتيب ڏنل ترتيب سان ترتيب ڏنو ويو آهي. مٿي کان وڌ کان وڌ عنصر اچي ٿو. ڇاڪاڻ ته اسٽيڪ LIFO ڊيٽا جو نمونو آهي ، محصول گهٽجڻ جي ترتيب ۾ لڳي ٿو.

2 1 4 3 6 5
6 5 4 3 2 1

الورورٿم

  1. شروعاتي اي اسٽيڪ ۽ ان ۾ عناصر کي دٻايو.
  2. عناصر کي اسٽيڪ ۾ ترتيب وار ترتيب سان داخل ڪرڻ لاءِ هڪ فنڪشن ٺاهيو جيڪو هڪ اسٽيڪ ۽ هڪ عنصر کي پيرا ميٽر جي طور تي قبول ڪري ٿو. چيڪ ڪريو ته اسٽيڪ خالي آهي يا ڏنل عنصر اسٽيڪ جي چوٽي تي عنصر کان وڏو آهي ، عنصر کي اسٽيڪ ۾ دٻايو ۽ واپس وڃو.
  3. عارضي تغير ٺاهيو ۽ ان ۾ اسٽيڪ جي چوٽي کي ذخيرو ڪريو. اسٽيڪ جي چوٽي تي عنصر کي پايو ۽ پنهنجو پاڻ تي تعريف واري ڪال ٺاهڻ. اسٽيڪ ۾ عارضي متغير کي زور ڏيو.
  4. اهڙي طرح ، هڪ فنڪشن قسم ٺاهيو () جيڪو اسٽيم کي پيرا ميٽر جي طور تي قبول ڪري ٿو. چيڪ ڪريو ته اسٽيڪ خالي ناهي ، ڪيبل هڪ ايڪس ٺاهيو ، ۽ ان ۾ اسٽيڪ جي چوٽي کي اسٽور ڪريو. اسٽيڪ جي چوٽي تي عنصر پايو. پنهنجو پاڻ کي ريٽرنس ڪال ڪريو. اسٽيڪ ۾ ترتيب وار عناصر ۾ عناصر داخل ڪرڻ لاءِ فنڪشن کي ڪال ڪريو.
  5. مکيه ۾ ترتيب وارو فنڪشن کي ڪال ڪريو ().
  6. ترتيب وار اسٽيڪ کي پرنٽ ڪرڻ لاءِ هڪ فنڪشن ٺاهيو جيڪو پيمراٽر کي اسٽيم قبول ڪري ٿو. لڪايو جڏهن اسٽيڪ خالي نه هئي ، اسٽيڪ جي ڊيٽا کي پرنٽ ڪريو ۽ ايندڙ عنصر ڏانهن منتقل ڪيو وڃي.

ڪوڊ

سي ++ پروگرام ترتيب ڏيڻ سان اسٽيڪ کي ترتيب ڏيڻ لاءِ

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

جاوا پروگرام ٻيهر ترتيب ڏيڻ سان اسٽيڪ کي ترتيب ڏيڻ لاءِ

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين ^ 2) جتي n اسٽوري ۾ عنصرن جو تعداد آهي. ڇاڪاڻ ته جڏهن اسان اسٽيڪ ۾ عنصر کي دٻايو ته اسان ختم ڪري سگهون ٿا تمام عنصر جيڪي هن وقت اسٽيڪ ۾ موجود آهن ۽ پوءِ ان کي داخل ڪريو. اهو ڪيس ٿئي ٿو جيڪڏهن انپٽ گهٽ ترتيب ۾ آهي.

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

اي (اين) ڇاڪاڻ ته اسان اين عنصرن لاءِ اسٽيڪ جاءِ استعمال ڪئي آهي. جڏهن ته اسان جو موجوده عنصر رکڻ لاءِ عنصرن کي هٽايو وڃي. اسان کي هٽائڻ وارن عنصرن کي اسٽور ڪرڻو هو ، جيڪو اسان کي هڪ لڪير واري جڳهه پيچيدگي ڏئي ٿو.