განლაგების განხორციელება ერთი რიგის გამოყენებით


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Fourkites Google Infosys MAQ microsoft
Queue დასტის

პრობლემის განცხადება

პრობლემა ”სტეკის განხორციელება ერთი რიგის გამოყენებით” გვთხოვს სტეკის (LIFO) მონაცემთა სტრუქტურის დანერგვას რიგის (FIFO) მონაცემთა სტრუქტურის გამოყენებით.

აქ LIFO ნიშნავს Last In First Out, ხოლო FIFO ნიშნავს First In First Out.

განლაგების განხორციელება ერთი რიგის გამოყენებით

მაგალითი

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

განმარტება

მოდით დავუშვათ, რომ რიგი გვაქვს და ახლა მასში ელემენტების დამატებას დავიწყებთ. ასე რომ მასში ელემენტების დამატება ან ჩასმა. ჩვენ დავურეკავთ ბიძგების ფუნქცია.

ბიძგი (1) —————> რიგის მიმდინარე მდგომარეობა -> 1

ბიძგი (2) —————> რიგის მიმდინარე მდგომარეობა -> 2,1

ამისათვის ჩვენ ამოვიღებთ ყველა ელემენტს, რომლებიც ადრე რიგში იყო. შემდეგ ჩვენს ახალ ელემენტს ჩასვამთ ცარიელ რიგში. ამის შემდეგ ჩვენ კვლავ ვუბიძგებთ ამოღებულ ელემენტებს იმავე თანმიმდევრობით.

რიგის ზედა / წინა მხარეს გადახედვა, ამრიგად, 2-ს გვაძლევს.

q.top () = 2

მოდით, ამოვიღოთ ზედა ელემენტი. ასე რომ, ჩვენ რიგიდან 2-ს ვხსნით.

მოხსნის შემდეგ, რიგის მიმდინარე მდგომარეობა = 1.

დასტის განსახორციელებლად ალგორითმი ერთი რიგის გამოყენებით

  1. კლასის სტეკის ინიციალიზაცია ა მდგომ მონაცემთა სტრუქტურა მთელი რიცხვი აკრიფეთ როგორც პირადი წევრი. ჩვენ ასევე განვსაზღვრავთ ბიძგი, პოპი, ტოპი, და ცარიელი რადგან ეს არის საზოგადოების წევრის ფუნქციები.
  2. შექმენით ფუნქცია ცარიელი (). დააბრუნე მართალი, თუ რიგი ცარიელია, სხვა შემთხვევაში დააბრუნე ყალბი.
  3. push () იღებს მთელი მნიშვნელობის მნიშვნელობას. შექმენით მთელი ცვლადი და შეინახეთ რიგის ზომა ცვლადში და დააჭირეთ / ჩასვით მთელი ცვლადი რიგში.
  4. გაიარეთ 0-დან რიგის წინა ზომაზე. განაგრძეთ რიგის ამჟამინდელი წინა მხარე თავისთვის ჩასმა და მოხსნა.
  5. შექმენით pop () ფუნქცია, რომელიც ამოწმებს რიგში ელემენტი არ არის, შემდეგ ბეჭდეთ "No Elements" და დააბრუნეთ -1. სხვა pop / ამოიღეთ ზედა / წინა ელემენტი.
  6. ჩვენ ვქმნით ფუნქციას top (), რომელიც უბრუნებს -1 თუ რიგში ელემენტი არ არის, სხვა შემთხვევაში დავაბრუნოთ რიგის წინა მხარე.

კოდი

C ++ პროგრამა სტეკის განსახორციელებლად ერთი რიგის გამოყენებით

#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

Java პროგრამა სტეკის განსახორციელებლად ერთი რიგის გამოყენებით

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

სირთულის ანალიზი

დროის სირთულე

push () ფუნქცია ხდება O (n) დრო, ხოლო pop () და top () ფუნქციები მოითხოვს მუდმივ დროს მხოლოდ ე.ი. O (1). იმის გამო, რომ ელემენტის გასაზრდელად ვიღებთ და ვამატებთ იმ ელემენტების რაოდენობას, რომლებიც მასში უკვე იმყოფებოდა. ეს ხდის ოპერაციას პოლინომის დროში.

სივრცის სირთულე

O (n) რადგან ჩვენ ვიყენებთ ადგილს n ელემენტების რაოდენობის შესანახად.