Спроведете оџак користејќи единечна редица


Ниво на тешкотија Лесно
Често прашувано во Амазон Фуркити Google Infosys MAQ Мајкрософт
редот Магацинот

Изјава за проблем

Проблемот „Спроведување на стек со користење на единствена редица“ бара од нас да спроведеме структура на податоци за стек (LIFO) користејќи структура на податоци за редици (FIFO).

Овде, LIFO значи Последен во Првиот аут додека 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

Објаснување

Да претпоставиме дека имаме редица и сега почнуваме да додаваме елементи во неа. Значи за додавање или вметнување на елементите во неа. Callе се јавиме на функција на притисок.

притисни (1) —————> моментална состојба на редицата -> 1

притисни (2) —————> моментална состојба на редицата -> 2,1

За да го направите ова, ќе ги отстраниме сите елементи што претходно беа во редот. Потоа го вметнуваме нашиот нов елемент во празната редица. После тоа, повторно ги туркаме отстранетите елементи во истиот редослед.

Гледајќи на горниот / предниот дел на редот, на тој начин ни дава 2 како резултат.

q.top () = 2

Да го отстраниме горниот елемент. Значи, ние отстрануваме 2 од редот.

Значи, по отстранувањето, моменталната состојба на редицата = 1.

Алгоритам за спроведување на оџакот со користење на единствена редица

  1. Иницијализирајте класен стек со a задача структура на податоци на број напишете како приватен член. Ние исто така дефинираме туркање, поп, врв, празни бидејќи тоа се функции на јавни членови.
  2. Создадете ја функцијата празна (). Врати се вистинито ако редот е празен друго вратете неточно.
  3. push () прифаќа цел број. Создадете целобројна променлива и зачувајте ја големината на редот во променливата и притиснете ја / вметнете ја целосната променлива во редот.
  4. Поминете од 0 до претходната големина на редот. Продолжете да го вметнувате тековниот фронт на редот кон себе и да го отстранувате.
  5. Создадете ја функцијата pop () која проверува дали нема елемент во редот, потоа отпечатете „Без елементи“ и вратете -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

Јава програма за спроведување на оџакот со користење на единствена редица

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 () трае Тој) време додека функциите поп () и горе () бараат само постојано време т.е. О (1). Бидејќи за туркање на елемент отстрануваме и додаваме број на елементи што веќе беа присутни во него. Ова ја прави операцијата да се извршува во полиномско време.

Комплексноста на просторот

Тој) затоа што користиме простор за складирање на n број на елементи.