数据结构与算法学习(0)--设计一个有getMin功能的栈

最近买了一本有关数据结构与算法的书(java实现),再结合之前的数据结构与算法的课程,来重新学习一下有关知识,并以代码的形式实现,达到加深理解的目的。

题目:
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元 素的操作。

要求:
1.pop、push、getMin操作时间复杂度都是O(1);
2.可以使用现成的栈结构

实现:
使用两个栈,一个存放正常的数据,一个存放最小值。每一次数据入栈,最小的值都会判断栈顶的值与其的大小,如果要入栈的数小的话,就将其压入栈中,大或等于的话就将栈顶的值压入最小栈中。

python3实现代码:
[cc lang="python"]

class stack(object):
def __init__(self): #初始化
self.item=[]
def pop(self): #出栈
return self.item.pop()
def push(self,item): #入栈
self.item.append(item)
def isempty(self): #判断是否为空
return self.item==[]
def peek(self): #返回栈顶元素
return self.item[len(self.item)-1]

#实现题目要求的栈
class stack2(object):
def __init__(self):
self.stackdata = stack()
self.stackmin = stack()
def push(self,item):
self.stackdata.push(item)
if self.stackmin.isempty():
self.stackmin.push(item)
return item
elif self.stackmin.peek() < item :
self.stackmin.push(self.stackmin.peek())
return self.stackmin.peek()
elif self.stackmin.peek() >= item:
self.stackmin.push(item)
return item
def pop(self):
data = self.stackdata.pop()
self.stackmin.pop()
return data

def seek(self):
return self.stackdata.peek()

def isempty(self):
return self.stackdata.item == []
def get_min(self):
return self.stackmin.peek()

if __name__ == '__main__': #测试所用
list_1 = [7, 5, 6, 5, 2, 3]
test = stack2()
for i in list_1:
data= test.push(i)
print("入栈:"+str(data)+" ")

for iu in list_1:
min_num = test.get_min()
out_num = test.pop()
print("最小值:"+str(min_num))
print("出栈:"+ str(out_num))
[/cc]

c++实现代码:
[cc lang="cpp"]
// stack.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
#include
#include

class stack2 {
public:
int push(int item);//入栈
int pop();//出栈
int seek();//返回栈顶的数
int get_min(); //返回最小的数
int isempty();//判断非空
private:
std::stack stackdata;
std::stack stackmin;

};
int main()
{
int length = 6;
int list_1[6] = { 7,5,6,5,2,3 };
stack2 test;
for (int tmp = 0; tmp < length; tmp++) //插入操作 { int data = test.push(list_1[tmp]); std::cout << "insert: " << data << std::endl; } for (int temp = 0; temp < length; temp++) { int min_number = test.get_min(); int pop_number = test.pop(); std::cout << "栈中最小的数是:" << min_number << std::endl; std::cout << "弹出的数是:" << pop_number << std::endl; } system("pause"); return 0; } int stack2::push(int item) //入栈 { if (stackdata.empty()) { stackdata.push(item); stackmin.push(item); } else { stackdata.push(item); int min_last = stackmin.top(); if (item < min_last) stackmin.push(item); else stackmin.push(min_last); } return item; } int stack2::pop() //出栈 { int tmp = stackdata.top(); stackdata.pop(); stackmin.pop(); return tmp; } int stack2::isempty() //判断非空 { return stackdata.empty(); } int stack2::seek() //数据栈顶的值 { return stackdata.top(); } int stack2::get_min() //最小栈的顶的值,同时也是题目要求实现的 { return stackmin.top(); } [/cc]

发表评论

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