Нэг дарааллыг ашиглан стекийг хэрэгжүүлэх


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Фуркайт Google-ийн Infosys MAQ Microsoft-
дараалал Stack

Асуудлын мэдэгдэл

"Нэг дарааллыг ашиглан стекийг хэрэгжүүлэх" асуудал нь биднээс дараалал (FIFO) өгөгдлийн бүтцийг ашиглан стек (LIFO) өгөгдлийн бүтцийг хэрэгжүүлэхийг шаарддаг.

Энд 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. Ангийн стекийг a дараалал өгөгдлийн бүтэц бүхэл тоо хувийн гишүүнээр бичнэ үү. Бид бас тодорхойлдог түлхэх, поп, дээд, болон хоосон байна энэ нь нийтийн гишүүний чиг үүрэг юм.
  2. Функцийг хоосон () үүсгэх. Хэрэв дараалал хоосон байвал үнэнийг буцаана уу, хэрэв худал бол буцаана.
  3. push () бүхэл тоон утгыг хүлээн авна. Бүхэл тоон хувьсагч үүсгэж, дарааллын хэмжээг хувьсагч дотор хадгалж, бүхэл тоон хувьсагчийг дараалалд оруулах / оруулах.
  4. 0-ээс дарааллын өмнөх хэмжээ рүү шилжүүл. Одоогийн дарааллын урд талыг өөртөө оруулаад арилгаж байгаарай.
  5. Дараалалд элемент байхгүй эсэхийг шалгадаг pop () функцийг үүсгээд дараа нь “No elements” гэж хэвлээд буцаана -1. Бусад поп / дээд / урд талын элементийг арилгах.
  6. Бид дараалалд ямар ч элемент байхгүй тохиолдолд -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 тооны элемент хадгалах зай ашиглаж байна.