Реалізуйте стек, використовуючи одну чергу


Рівень складності Легко
Часто запитують у Амазонка Фуркіти Google Infosys MAQ Microsoft
Чергу Стек

Постановка проблеми

Проблема «Реалізувати стек за допомогою однієї черги» просить нас реалізувати структуру даних стеку (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

Пояснення

Припустимо, у нас є черга, і тепер ми починаємо додавати в неї елементи. Тож для додавання або вставки елементів у нього. Ми зателефонуємо до функція натискання.

push (1) —————> поточний стан черги -> 1

push (2) —————> поточний стан черги -> 2,1

Для цього ми видалимо всі елементи, які раніше були в черзі. Потім ми вставляємо наш новий елемент у порожню чергу. Після цього ми знову натискаємо вилучені елементи в тому ж порядку.

Дивлячись на верх / фронт черги, таким чином ми отримуємо 2 як результат.

q.top () = 2

Вилучимо верхній елемент. Отже, ми вилучаємо 2 із черги.

Отже, після видалення поточний стан черги = 1.

Алгоритм реалізації стека за допомогою однієї черги

  1. Ініціалізуйте стек класів за допомогою чергу структура даних ціле тип як приватний член. Ми також визначаємо push, pop, top, і порожній оскільки це публічні функції членів.
  2. Створіть функцію empty (). Повернути true, якщо черга порожня, else return false.
  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 () вимагають постійного часу, тобто O (1). Тому що для проштовхування елемента ми видаляємо і додаємо кількість елементів, які вже були в ньому. Це змушує операцію виконуватись у поліноміальному часі.

Складність простору

О (п) тому що ми використовуємо простір для зберігання n кількості елементів.