Истифодаи стекро бо истифода аз навбати ягона


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Фуркайтҳо Google Infosys MAQ Microsoft
навбат тӯда

Изҳороти мушкилот

Мушкилоти «Татбиқи стек бо истифодаи як навбат» аз мо хоҳиш мекунад, ки сохтори маълумотҳои стек (LIFO) -ро бо истифода аз сохтори маълумотҳои навбат (FIFO) татбиқ намоем.

Дар ин ҷо LIFO маънои Last In First Out ва FIFO маънои Аввалин дар аввал баромаданро дорад.

Истифодаи стекро бо истифода аз навбати ягона

мисол

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. Функсияи empty () -ро эҷод кунед. Бозгаштан ҳақиқӣ, агар навбат холӣ бошад вагарна бардурӯғ баргардед.
  3. push () арзиши бутунро қабул мекунад. Тағйирёбандаи бутун эҷод кунед ва андозаи навбатро дар тағирёбанда нигоҳ доред ва тағирёбандаи бутунро дар навбати худ гузоред / дохил кунед.
  4. Аз 0 ба андозаи қаблии навбат гузаред. Пеши навбатро ба худ гузоред ва тоза кунед.
  5. Функсияи pop () -ро эҷод кунед, ки оё ягон элемент дар навбат набудани онро месанҷад, пас "No elements" -ро чоп кунед ва -1 баргардонед. Дигар поп / хориҷ кардани унсури боло / пеши.
  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 () иҷро шуда истодааст Эй (н) вақт ҳангоми функсияҳои pop () ва top () танҳо вақти доимиро талаб мекунад, яъне О (1). Зеро барои тела додани унсур мо шумораи унсурҳои дар он мавҷудбударо хориҷ ва илова мекунем. Ин амалиётро дар вақти бисёрзанӣ иҷро мекунад.

Мураккабии фазо

Эй (н) зеро мо ҷойро барои нигоҳ доштани n шумораи унсурҳо истифода мебарем.