题目:
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
C++实现:
输入格式是:
1 10
2
1 代表push,后面的数字是要push的内容,2代表pop
代码如下:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
template <class T>
class MinStackElement
{
public:
T data; // the data stored
T min; // the minimum element under the current element
};
template <class T>
class MinStack
{
public:
MinStack(int max_size);
void push(T new_data);
T pop();
T minElement();
private:
MinStackElement<T> *elements;
int size;
int top;
};
template <class T>
MinStack<T>::MinStack(int max_size)
{
elements = new MinStackElement<T>[max_size];
size = max_size;
top = 0;
}
template <class T>
void MinStack<T>::push(T new_data)
{
top ++;
elements[top - 1].data = new_data;
if(top == 1)
{
elements[top - 1].min = new_data;
}
else
{
if(new_data < elements[top - 2].min)
{
elements[top - 1].min = new_data;
}
else
{
elements[top - 1].min = elements[top - 2].min;
}
}
}
template <class T>
T MinStack<T>::pop()
{
if(top == 0)
return T();
T value;
value = elements[top - 1].data;
top --;
return value;
}
template <class T>
T MinStack<T>::minElement()
{
return elements[top - 1].min;
}
int main() {
ifstream fin ("minstack.in");
ofstream fout ("minstack.out");
int instruction, num;
MinStack<int> min_stack(50);
if(fin.good() == false)
{
fout << "file open failed" << endl;
return 0;
}
while(true)
{
if(fin.eof())
break;
fin >> instruction;
if(instruction == 1)
{
fin >> num;
min_stack.push(num);
fout << "push : " << num << ", the minimum element : " << min_stack.minElement() << endl;
}
else if(instruction == 2)
{
num = min_stack.pop();
fout << "pop : " << num << ", the minimum element : " << min_stack.minElement() << endl;
}
}
}
样例输入:
1 10
1 4
1 11
1 5
1 8
1 90
2
2
1 6
1 2
1 30
2
2
样例输出:
push : 10, the minimum element : 10
push : 4, the minimum element : 4
push : 11, the minimum element : 4
push : 5, the minimum element : 4
push : 8, the minimum element : 4
push : 90, the minimum element : 4
pop : 90, the minimum element : 4
pop : 8, the minimum element : 4
push : 6, the minimum element : 4
push : 2, the minimum element : 2
push : 30, the minimum element : 2
pop : 30, the minimum element : 2
pop : 2, the minimum element : 4
原文链接: https://www.cnblogs.com/waytofall/archive/2012/04/09/2439451.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/46499
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!