Q: 如何设计一个特殊的栈,支持min()操作,返回栈中的最小元素.
这个问题来源于去年面试遇到的一道题目,面试官给了20分钟时间让设计这样一个栈.当时时间有限,虽然写出来了一个版本,但是那个版本还存在很多的问题,比如不够通用,只能支持int类型数据;同时,效率也不高, 存在大量的数据拷贝.
面试完后又仔细思考了一下,重新写了一个版本,记录一下,分享给大家！这个版本主要解决前面说的两个问题,1.通用性;2.效率.
1. 接口设计
既然要解决通用性的问题,让这个栈支持所有的数据类型,必须使用template.
同时,为了支持min()操作,我们需要两个数组.数组a保存push到栈中的数据,数组b记录最小值,数组a每做一次更新(push或者pop),数组b都要随之更新.
再仔细想一下,数组b真的需要保存最小值吗?其实在数组a中已经有了最小值得一份拷贝,在b数组中再存一次会造成空间浪费,而且如果存储在栈中的是一个非常庞大的类类型,把该类型数据写入b数组也是相当耗时的.这样就造成了空间和时间上的双重浪费,显然这是不合理的.事实上,在b数组中完全没有必要存储实际的类对象,只要存储一下该对象在a数组中的索引就可以了,这样既节省空间,又提高了速度.
基于上面的分析,我们可以设计下面的接口.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| template <class T>
class stack
{
private:
int top;
int minTop;
T buf[1024];
int minIndex[1024];
const int maxsize = 1024;
public:
int push(const T& item);
T pop();
int pushMinIndex(const T& item);
int popMinIndex();
T min();
stack();
stack(const stack& s);
stack& operator=(const stack& s);
~stack();
};
|
2.接口实现
基于上面的设计,我们可以轻松写出代码来.
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
| #ifndef MY_STACK_H
#define MY_STACK_H
#include<cassert>
#define ERROR -1
#define OK 0
template <class T>
class stack
{
private:
int top;
int minTop;
T buf[1024];
int minIndex[1024];
const int maxsize = 1024;
public:
int push(const T& item);
int pushMinIndex(const T& item);
int popMinIndex();
T min();
T pop();
stack();
stack(const stack& s);
stack& operator=(const stack& s);
~stack();
};
template<class T>
stack<T>::stack():top(-1), minTop(-1)
{
}
template<class T>
stack<T>::~stack() {}
template<class T>
int stack<T>::push(const T& item)
{
top++;
if ((top >= maxsize) || (top < 0)) {
return ERROR;
}
buf[top] = item;
pushMinIndex(item);
return OK;
}
template<class T>
T stack<T>::pop()
{
assert(top >= 0);
popMinIndex();
return buf[top--];
}
template<class T>
int stack<T>::pushMinIndex(const T& item)
{
minTop++;
if ((minTop >= maxsize) || (minTop < 0)) {
return ERROR;
}
if (minTop == 0) {
minIndex[minTop] = top;
return OK;
}
if (item < buf[minIndex[minTop - 1]]) {
minIndex[minTop] = top;
} else {
minIndex[minTop] = minIndex[minTop - 1];
}
return OK;
}
template<class T>
int stack<T>::popMinIndex()
{
minTop--;
return OK;
}
template<class T>
T stack<T>::min()
{
assert(minTop >= 0);
return buf[minIndex[minTop]];
}
template<class T>
stack<T>::stack(const stack<T>& s):top(s.top), minTop(s.minTop)
{
top = s.top;
minTop = s.minTop;
for (int i = 0; i <= top; i++) {
buf[i] = s.buf[i];
}
for (int i = 0; i <= minTop; i++) {
minIndex[i] = s.minIndex[i];
}
}
template<class T>
stack<T>& stack<T>::operator=(const stack<T>& s)
{
top = s.top;
minTop = s.minTop;
for (int i = 0; i <= top; i++) {
buf[i] = s.buf[i];
}
for (int i = 0; i <= minTop; i++) {
minIndex[i] = s.minIndex[i];
}
return *this;
}
#endif
|
3. 测试一下
我们写一个小例子测试一下自己写的stack是否好用.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
#include "minstack.hpp"
using namespace std;
int main()
{
stack<double> s;
double a[] = {8.1, 7.2, 9.5, 6.3, 2.5, 5.6, 3.5};
for (int i = 0; i < 7; i++) {
s.push(a[i]);
cout << s.min() << " ";
}
cout << endl;
stack<double> t;
t = s;
cout << "---------------------------" << endl;
for (int i = 0; i < 7; i++) {
cout << t.min() << " ";
t.pop();
}
return 0;
}
|
编译一下
运行结果
1
2
3
4
| $ ./a.out
8.1 7.2 7.2 6.3 2.5 2.5 2.5
---------------------------
2.5 2.5 2.5 6.3 7.2 7.2 8.1
|
看起来没什么问题哦~
代码已上传至github，链接在此
https://github.com/zkangHUST/CppSTL
THE END.