Реализуйте стек с использованием единой очереди


Сложный уровень Легко
Часто спрашивают в Амазонка Фуркиты 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. Инициализируйте стек классов с помощью очередь структура данных целое введите как частный член. Мы также определяем толкать, поп, сверху, и пустой поскольку это общедоступные функции-члены.
  2. Создайте функцию empty (). Верните true, если очередь пуста, иначе верните 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 элементов.