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

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

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

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

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


Листинг C++

#include <stack>
using namespace std;

class stack_min
{
private :
    class elem
    {
    public :
        int a, m;
        elem (int _a = 0, int _m = 0) : a (_a), m (_m) {};
    };    
    stack < elem > s;
    
public :
    
    void pop ()
    {
        s.pop ();
    }
    int minimum ()
    {
        return s.size () <= 0 ? 1e9 : s.top ().m;
    }
    void push (int x)
    {
        s.push (elem (x, min (x, minimum ())));
    }
};


13:37
05.08.2009