# CCI题目3-2：Min Stack

By | 2012 年 11 月 19 日

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

<

pre>

//
// main.cpp
// CCI.3.2.Min Stack
//
// Created by Qiu Xiangyu on 12-11-19.
//

# include

using namespace std;

template
class stackNode {
public:
Ts value;
stackNode pre;
stackNode *min;
stackNode() {pre = NULL;}
stackNode(Ts&avalue, stackNode
thePre):value(avalue),pre(thePre) {;}
};

template
class minStack {
int _size;
stackNode *_top;
public:
minStack() {
_size = 0;
_top = NULL;
}
void push(T value) {
stackNode *newnode = new stackNode(value,_top);
stackNode *minnode = newnode;
if (_top && _top->min->value < minnode->value) {
minnode = _top->min;
}
newnode->min = minnode;
_top = newnode;
}
void pop() {
if (_top) {
stackNode *lastNode = _top;
_top = lastNode->pre;
delete lastNode;
}
}
T *top() {
if (_top) {
return &_top->value;
}
return NULL;
}
T *min() {
if (_top) {
return &_top->min->value;
}
return NULL;
}
};

int main(int argc, const char * argv[])
{
std::cout << “Hello\n”;
minStack teststack;
for (int i = 0; i < 10; ++i) {
teststack.push(10 – i);
}
for (int i = 0; i < 10; ++i) {
teststack.push(i);
}
while (teststack.top()) {
int val = teststack.top();
cout<<“v(“<<val<<“),m(“<<
teststack.min()<<“)\n”;
teststack.pop();
}
return 0;
}