CCI题目3-2:Min Stack

By | 2012 年 11 月 19 日

开始想的只需要track每个push进来的条目,就可以在O(1)返回最小元素了。push()没问题,但是pop()的时候就遇到问题了,需要知道pop了这个元素之后的下一个最小的元素是谁。。。

于是就在每一个stackNode上设置一个pointer来track当这个stackNode在最顶端的时候,此时的最小栈位置。这样就可以pop(),push(),min()都是O(1)了。



题目
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注