Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Очередь с поддержкой минимума всех элементов

Необходимо реализовать структуру данных, которая за O(1) добавляет элемент в множество, извлекает из него первый добавленный элемент и находит минимум всех элементов множества.

    Будем использовать два стека с поддержкой минимума. В один стек мы будем добавлять элементы, а из другого извлекать. Когда в стек, из которого мы извлекаем элементы, окажется пуст, то переписываем все элементы из другого стека в него. Минимум будет равен минимальному из минимумов обоих стеков.


Листинг C++

#include <stack>
using namespace std;

class queue_min
{
private :
    stack_min s1, s2;
public :
    void pop ()
    {
        if (s1.size ())
            s1.pop ();
        else
        {
            while (s2.size ())
            {
                s1.push (s2.top ());
                s2.pop ();
            }
            if (s1.size ())
                s1.pop ();
        }
    }
    void push (int x)
    {
        s2.push (x);
    }
    int minimum ()
    {
        return min (s1.minimum (), s2.minimum ());
    }
};


13:57
05.08.2009