设计一个有getMin功能的栈（C++）
设计一个有getMin功能的栈
【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈种最小元素的操作。
【要求】
- pop、push、getMin操作的时间复杂度都是 O(1)。
- 设计的栈类型可以使用现成的栈结构。
【C++实现】
方法一
使用两个栈，一个正常保存数据：stack_Data，另一个用于保存当前情况下的最小值：stack_Min。
压栈情况：
- 当Min栈空的时候直接压入。
- 当Min非空时候，Min栈顶元素要保持是在Data栈中最小的，因此压栈的时候需要进行比较。当压栈元素小于等于Min栈栈顶元素时，说明压栈元素在压栈后将成为当前最小值，因此需要一起压入Min栈中。
- Data栈无论何时都需要压栈。
弹栈情况：
- 当Data栈非空时直接弹栈。
- 当Data栈弹出的元素等于Min栈顶元素时，Min栈需要一并弹出。
代码实现：
头函数MyStack.h：
#pragma once
#include <stack>
using namespace std;
class MyStack {
public:
//用于保存数据
stack<int> stack_Data;
//用于保存当前最小值
stack<int> stack_Min;
//弹栈
void pop() {
if (!stack_Data.empty()) {
int num = stack_Data.top();
stack_Data.pop();
if (num == getMin()) {
stack_Min.pop();
}
}
else
throw new exception("【空栈】：弹出失败！");
}
//压栈
void push(int number) {
if (stack_Min.empty())
stack_Min.push(number);
else if (number <= getMin()) {
stack_Min.push(number);
}
stack_Data.push(number);
}
//得到最小值
int getMin() {
if (stack_Min.empty())
throw new exception("【空栈】：无最小值！");
return stack_Min.top();
}
};
主函数main.cpp：
// 设计一个有getMin功能的栈.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include "MyStack.h"
using namespace std;
int main(){
cout << "|-------------------------------------------------|" << endl;
cout << "| 1. 压栈 |" << endl;
cout << "| 2. 弹栈 |" << endl;
cout << "| 3. 当前最小元素 |" << endl;
cout << "| 4. 退出 |" << endl;
cout << "|-------------------------------------------------|" << endl;
MyStack mystack;
while (1) {
int num;
cin >> num;
int min;
switch (num)
{
case 1:
cout << "请输入压栈元素：";
int number;
cin >> number;
mystack.push(number);
cout << endl;
break;
case 2:
mystack.pop();
cout << "弹栈成功！" << endl;
break;
case 3:
min = mystack.getMin();
cout << "当前最小值：" << min << endl;
break;
case 4:
return 0;
}
}
}
方法二
与一相类似，区别在于是否当压栈元素大于Min栈顶元素时，方法一是不进行压栈操作的，而方法二将会进行压栈操作，所压栈的元素是当前最小值（也就是Min栈顶元素）。
对于弹栈操作，方法一需要进行判断是否当前弹栈元素是当前最小值，而方法二直接弹出即可，无需判断。
但无论方法一还是方法二，时间复杂度都是O(1)，空间复杂度都是O(n)。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-09-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读