1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| //
| // Created by Scheaven on 2020/6/8.
| //
|
| #ifndef _STACK_UTIL_H
| #define _STACK_UTIL_H
|
| #include <algorithm>
| #include <memory.h>
| #include <iostream>
| #include <fstream>
| #include <string>
| #include <iomanip>
| #include <stdlib.h>
| #include <vector>
| #include <stack>
| #include <cstdio>
|
| using namespace std;
|
| /**实现最大值栈
| 以O(1)的时间查询栈中的最大值.
| 算法思路
| 维护一个最大值栈，在原栈中数据发生改变时最大值栈也跟着改变。
| 每次输入一个数据，若最大值栈为空，则比较最大值栈栈顶和当前元素，如果当前元素较大或相等，就把当前元素推入栈中，反之出栈时，如果出栈元素和当前元素相等，则把最大值栈中元素也推出栈。
| */
|
| template <typename T> //注意 泛型模板必须把实现方法直接写在头文件里 否则找不到文件定义
| class MaxStack
| {
| private:
| stack<T> max_stack;
| stack<T> _data;
|
| public:
| MaxStack(){};
| ~MaxStack(){};
|
|
| void push(T ele) //压入
| {
| _data.push(ele);
| if(max_stack.empty() || ele>=max_stack.top())
| {
| max_stack.push(ele);
| }
| };
|
| void pop() //弹出
| {
| T tem = _data.top();
| _data.pop();
| if(tem==max_stack.top())
| {
| max_stack.pop();
| }
| };
|
| T top() //获取第一个元素
| {
| return _data.top();
|
| };
|
| bool isEmpty()
| {
| return _data.empty();
| };
|
| T maxItem() //取最大元素
| {
| return max_stack.top();
| };
|
| int size() //个数
| {
| return _data.size();
| };
| };
|
|
| template <typename T> //注意 泛型模板必须把实现方法直接写在头文件里 否则找不到文件定义
| class MinStack
| {
| private:
| stack<T> min_stack;
| stack<T> _data;
|
| public:
| MinStack(){};
| ~MinStack(){};
|
| void push(T ele) //压入
| {
| _data.push(ele);
| if(min_stack.empty() || ele<=min_stack.top())
| {
| min_stack.push(ele);
| }
| };
|
| void pop() //弹出
| {
| T tem = _data.top();
| _data.pop();
| if(tem==min_stack.top())
| {
| min_stack.pop();
| }
| };
|
| T top() //获取第一个元素
| {
| return _data.top();
|
| };
|
| bool isEmpty()
| {
| return _data.empty();
| };
|
| T minItem() //取最大元素
| {
| return min_stack.top();
| };
|
| int size() //个数
| {
| return _data.size();
| };
| };
|
| #endif //INC_05_MAX_STACK_QUEUE_STACK_UTIL_H
|
|
