定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push、及pop的时间复杂度都是O(1)。
创新互联成立于2013年,是专业互联网技术服务公司,拥有项目成都网站制作、成都做网站、外贸营销网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元滁州做网站,已为上家服务,为滁州各地企业和个人服务,联系电话:18982081108
首先,栈的特点是“先进后出,后进先出”,因此,对于pop和push两个操作自然都是直接放入栈顶和直接在栈顶删除元素,那么如果要找栈中的最小值min,因为要求时间复杂度为O(1),因此肯定不能遍历栈找出最小元素,这里可以想到使用在这个栈的数据结构中使用两个栈,一个栈用来正常的存放删除数据,另一个栈就用来存放当前栈中的最小值;
当第一次push进栈的时候,就将数据也push进min栈中,并且min栈中的栈顶元素为当前栈的最小值,当push的数据比min栈中的栈顶元素小的时候,就将push的数据也放进min栈中,当push的数据比min栈中的栈顶元素大的时候,就在再次将min栈中的栈顶元素再压进栈,因此,这样下去,min栈中栈顶元素始终为当前数据栈的最小值;而进行pop数据的时候,在pop数据栈的栈顶元素时也pop出min栈的栈顶元素,这样的话还是保证了min栈中栈顶元素为最小值,且时间复杂度为O(1);
上述内容可画图如下:
程序设计如下:
#include#include using namespace std; template class my_stack { public: my_stack()//栈的默认构造函数,开始时指针为空且将容量设计为3 :_data(NULL) ,_min(NULL) ,_size(0) ,_capacity(3) {} void my_push(T data)//push数据 { if(_data == NULL)//当第一次放数据时 { _data = new T[_capacity]; _min = new T[_capacity]; _data[_size] = data; _min[_size++] = data; return; } _CheckCapacity();//检查容量 _data[_size] = data; if(data < _min[_size-1])//若果要放入的数据比栈顶元素小,直接放入,否则,再次放入栈顶元素 _min[_size] = data; else _min[_size] = _min[_size-1]; ++_size; } void my_pop()//pop数据 { if(_data == NULL) return; --_size; } T& min()//取出最小值 { if(_data == NULL) { cout<<"no data..."< stack; stack.my_push(3); stack.my_push(5); stack.my_push(1); stack.my_push(2); stack.my_push(0); stack.my_push(6); stack.print_stack(); cout<<"min data: "< 运行程序:
可以看到,每pop一次数据,都能输出当前栈中的最小值,且时间复杂度都为O(1)。
《完》
名称栏目:包含min函数的栈——21
地址分享:http://bjjierui.cn/article/jgosgg.html