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 | } |