View difference between Paste ID: jRRCdtXM and rkV2zYna
SHOW: | | - or go back to the newest paste.
1
#include <iostream>
2
#include <vector>
3
#include <numeric>
4
#include <algorithm>
5
6
using namespace std;
7
8
template <typename It>
9
void PrintRange(It range_begin, It range_end) {
10
    for (auto it = range_begin; it != range_end; ++it) {
11
        cout << *it << " "s;
12
    }
13
    cout << endl;
14
}
15
16
template <typename Type>
17
class StackMin {
18
public:
19
    void Push(const Type& element) {
20
        elements_.push_back(element);
21
        if (min_.empty() || !(element>min_el_)){
22
            min_el_ = element;
23
        }
24
        min_.push_back(make_pair(element,min_el_));
25
    }
26
    void Pop() {
27
        if (!elements_.empty()){
28
            min_.pop_back();
29
            min_el_ = min_.back().second; //? 
30
            elements_.pop_back();
31
        }
32
    }
33
    const Type& Peek() const {
34
        return elements_.back();
35
    }
36
    Type& Peek() {
37
        return elements_.back();
38
    }
39
    void Print() const {
40
        PrintRange(elements_.begin(), elements_.end());
41
    }
42
    uint64_t Size() const {
43
        return elements_.size();
44
    }
45
    bool IsEmpty() const {
46
        return elements_.empty();
47
    }
48
    const Type& PeekMin() const {
49
        return min_el_;
50
    }
51
    Type& PeekMin() {
52
        return min_el_;
53
    }
54
private:
55
    vector<Type> elements_;
56
    vector<pair<Type, Type>> min_;
57
    Type min_el_;
58
}; 
59
60
int main() {
61
    StackMin<int> stack;
62
    vector<int> values(5);
63
    // заполняем вектор для тестирования нашего стека
64
    iota(values.begin(), values.end(), 1);
65
    // перемешиваем значения
66
    random_shuffle(values.begin(), values.end());
67
    // заполняем стек
68
    for (int i = 0; i < 5; ++i) {
69
        stack.Push(values[i]);
70
    }
71
    // печатаем стек и его минимум, постепенно убирая из стека элементы
72
    while (!stack.IsEmpty()) {
73
        stack.Print();
74
        cout << "Минимум = "s << stack.PeekMin() << endl;
75
        stack.Pop();
76
    }
77
}