Tək növbədən istifadə edərək bir yığın tətbiq edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Fourkites google Infosys MAQ microsoft
Queue QalaqBaxılıb 34

Problem bəyanat

Problem "Bir sıra istifadə edərək bir yığını tətbiq etmə" problemi, bir sıra (FIFO) məlumat quruluşundan istifadə edərək bir yığın (LIFO) məlumat quruluşunu tətbiq etməyimizi tələb edir.

Burada LIFO Son Giriş Birincisi deməkdir, FIFO İlk Çıxış Birincisi deməkdir.

Tək növbədən istifadə edərək bir yığın tətbiq edinPin

misal

push(10)
push(20)
top()
pop()
push(30)
pop()
top()
Top : 20
Pop : 20
Pop : 30
Top : 10
push(1)
push(2)
top()
pop()
Top : 2
Pop : 2

Izahat

Tutaq ki, növbəmiz var və indi elementlər əlavə etməyə başlayırıq. Buna görə elementləri əlavə etmək və ya əlavə etmək üçün. Biz zəng edəcəyik push funksiyası.

bas (1) —————> növbənin cari vəziyyəti -> 1

bas (2) —————> növbənin cari vəziyyəti -> 2,1

Bunu etmək üçün əvvəllər növbədə olan bütün elementləri siləcəyik. Sonra yeni elementimizi boş növbəyə əlavə edirik. Bundan sonra çıxarılan elementləri yenidən eyni qaydada itələyirik.

Növbənin yuxarı / ön hissəsinə baxaraq nəticədə bizə 2 verir.

q.top () = 2

Üst elementi götürək. Beləliklə 2-ni növbədən çıxarırıq.

Yəni qaldırıldıqdan sonra növbənin cari vəziyyəti = 1.

Tək növbədən istifadə edərək bir yığını tətbiq etmək üçün alqoritm

  1. A ilə bir yığın başlayın queue məlumatların strukturu tam xüsusi üzv kimi yazın. Biz də təyin edirik bas, pop, üst, boş ictimai üzv funksiyaları olduğu üçün.
  2. Boş () funksiyasını yaradın. Sıra boş olduqda doğru qayıdın başqa halda false qayıdın.
  3. push () bir tam dəyər qəbul edir. Bir tam dəyişən yaradın və növbənin ölçüsünü dəyişəndə ​​saxlayın və tam dəyişəni növbəyə daxil edin / daxil edin.
  4. 0-dan növbənin əvvəlki ölçüsünə keçin. Növbənin indiki qabağını özünə əlavə etməyə və götürməyə davam edin.
  5. Növbədə heç bir elementin olmadığını yoxlayan pop () funksiyasını yaradın, sonra “Elements yoxdur” yazıb -1 qaytarın. Başqa bir pop / üst / ön elementi çıxarın.
  6. Sırada heç bir element olmadığı təqdirdə -1 qaytaran funksiya top () yaradırıq, başqa növbənin ön hissəsini geri qaytarırıq.

Kodu

Tək növbə istifadə edərək bir yığın tətbiq etmək üçün C ++ Proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
class Stack{ 
    queue<int>q;
    
public: 
    void push(int val); 
    int pop(); 
    int top(); 
    bool empty(); 
}; 
  
void Stack::push(int val){ 
    int s = q.size(); 
  
    q.push(val); 
  
    for(int i=0; i<s; i++){ 
        q.push(q.front()); 
        q.pop(); 
    } 
} 
  
int Stack::pop(){ 
    if(q.empty()){ 
        cout<<"No elements\n";
        return -1;
    }    
    else{
        int x = q.front();
        q.pop();
        return x;
    }  
} 
  
int  Stack::top(){ 
    return (q.empty())? -1 : q.front(); 
} 
  
bool Stack::empty(){ 
    return (q.empty()); 
} 
  
int main(){ 
    Stack s;
    
    s.push(10); 
    s.push(20); 
    cout<<"Top : "<<s.top()<<endl; 
    cout<<"Pop : "<<s.pop()<<endl; 
    s.push(30); 
    cout<<"Pop : "<<s.pop()<<endl;
    cout<<"Top : "<<s.top()<<endl; 

    return 0; 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

Tək növbə istifadə edərək bir yığını tətbiq etmək üçün Java Proqramı

import java.util.LinkedList; 
import java.util.Queue; 
  
class stack{ 
    Queue<Integer> q = new LinkedList<Integer>(); 
      
    void push(int val){ 
        int size = q.size(); 
          
        q.add(val); 
          
        for(int i=0; i<size; i++){ 
            int x = q.remove(); 
            q.add(x); 
        } 
    } 
      
    int pop(){ 
        if (q.isEmpty()){ 
            System.out.println("No elements"); 
            return -1; 
        } 
        int x = q.remove(); 
        return x; 
    } 
      
    int top(){ 
        if (q.isEmpty()) 
            return -1; 
        return q.peek(); 
    } 
      
    boolean isEmpty(){ 
        return q.isEmpty(); 
    } 
  
    public static void main(String[] args){ 
        stack s = new stack(); 
        
        s.push(10); 
        s.push(20); 
        System.out.println("Top : " + s.top()); 
        System.out.println("Pop : " + s.pop()); 
        s.push(30); 
        System.out.println("Pop : " + s.pop()); 
        System.out.println("Top : " + s.top());
        
    } 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

push () funksiyası davam edir O (n) zaman pop () və top () funksiyaları yalnız daimi vaxt tələb edir, yəni O (1). Çünki bir elementi itələmək üçün onsuz da mövcud olan elementlərin sayını çıxarırıq və əlavə edirik. Bu, əməliyyatı polinom vaxtında işləməyə məcbur edir.

Kosmik Mürəkkəblik

O (n) n element sayını saxlamaq üçün yerdən istifadə etdiyimiz üçün.

Translate »
1