【25】实现一个含有min函数的栈的通用模板

简介: 题目:设计一个栈类型,使得在该栈类型中有一个函数min可以得到栈的最小元素,要求这个栈的push、pop、min都是O(1)。分析:1. 栈的性质是先进后出,因此一般情况下栈的push、pop的时间是O(1),但是要求栈的min必须要枚举整个栈,时间复杂度为O(n)2.


题目:设计一个栈类型,使得在该栈类型中有一个函数min可以得到栈的最小元素,要求这个栈的push、pop、min都是O(1)。

分析:

1. 栈的性质是先进后出,因此一般情况下栈的push、pop的时间是O(1),但是要求栈的min必须要枚举整个栈,时间复杂度为O(n)

2. 题目要求设计一个栈在O(1)的时间内找到min,我们要想到一个方法来满足,先看一个例子

3. 从下面的表中我们可以很清楚的看到,我么需要维护一个保存min的栈,并且这个栈和我们的数据栈是一起变化的,因此我们可以利用两个栈来模拟实现这个过程

操作

栈的元素(左边栈顶)

最小值

第一次

Push 5

5

5

第二次 

Push 6

6 5

5

第三次

Push 4

4 6 5

4

第四次

Push 7

7 4 6 5

4

第五次

Push 9

9 7 4 6 5

4

第六次

Pop

7 4 6 5

4

第七次

Pop

4 6 5

4

第八次

Pop

6 5

5

第九次

Pop

5

5


4. 示例代码

//实现含有min的栈类模板
template <typename T>
class Stack{
public:
	Stack(void);
	~Stack(void){}
	//声明函数
	void Push(const T& value);
	void Pop(void);
	T Min(void);
private:
	stack<T> dataStk;
	stack<T> minStk;
};

//实现构造函数
template <typename T> Stack<T>::Stack(void){
    //清空两个栈
	while(!dataStk.empty()){
		dataStk.pop();
	}
	while(!minStk.empty()){
		minStk.pop();
	}
}

//实现Push
template <typename T> void Stack<T>::Push(const T& value){
	dataStk.push(value);
	//如果是空栈直接插入,不能通过取栈顶元素比较
	if(minStk.empty()){
		minStk.push(value);
	}
	else{
	    T minValue = minStk.top();
	    if(minValue > value){
	       minValue = value;
	    }
	    //插入到minStk中
        minStk.push(minValue);
	}
}

//实现Pop函数
template <typename T> void Stack<T>::Pop(void){
    //如果是空栈报异常
	if(dataStk.empty()){
	    throw exception("error");
	}
	else{
		dataStk.pop();
		minStk.pop(); //同时删除minStk栈顶元素
	}
}

//实现Min函数
template <typename T> T Stack<T>::Min(void){
	//如果空栈返回异常
	if(minStk.empty()){
	    throw exception("error");
	}
	else{
		return minStk.top();
	}
}



相关文章
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
158 77
|
3天前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
16 4
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
43 7
|
4月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
375 9
|
4月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
64 1
|
2月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
50 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
51 9
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
128 21
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等