【说明】:
本文是左程云老师所著的《程序员面试代码指南》第一章中“设计一个有getMin功能的栈”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
【要求】:
1、pop、push、getMin操作的时间复杂度都是O(1)。
2、设计的栈类型可以使用现成的栈结构。
【思路】:
以空间换时间:总体设计上采用两个栈,一个栈保存元素,另一个栈保存每一步的最小值。
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
1、声明代码
/*
*文件名:
*作者:Stan
*摘要:设计一个具有O(1)复杂度的栈,并实现其基本操作
*/
#ifndef _GETMINSTACK_H
#define _GETMINSTACK_H
#include <stack>
using namespace std;
class MyStack
{
public:
MyStack(){};
~MyStack(){};
void push(int data);
void pop();
int top();
int getMin();
bool empty();
private:
stack<int> sData;
stack<int> sMin;
};
#endif
View Code
2、实现代码
/*
*文件名:
*作者:Stan
*摘要:MyStack.h中声明的实现
*/
#include "getMinStack.h"
#include <stdexcept>
#include <exception>
void MyStack::push(int data)
{
if(sMin.empty())
sMin.push(data);
else if(data < sMin.top())
sMin.push(data);
else
sMin.push(sMin.top());
sData.push(data);
return ;
}
void MyStack::pop()
{
if(sData.empty())
throw runtime_error("Empty Stack!");
sMin.pop();
sData.pop();
}
int MyStack::top()
{
if(sData.empty())
throw runtime_error("Empty Stack!");
return sData.top();
}
int MyStack::getMin()
{
if(sMin.empty())
throw runtime_error("Empty Stack!");
return sMin.top();
}
bool MyStack::empty()
{
if(sData.empty())
return true;
else
return false;
}
View Code
3、测试代码
/*
*文件名:
*作者:Stan
*摘要:测试函数
*/
#include "getMinStack.h"
#include <iostream>
using namespace std;
int main()
{
int a[]={3,4,5,1,2,1};
MyStack s;
for(int i=0;i<6;i++)
{
s.push(a[i]);
cout << "s.top():" << s.top() << endl;
cout << "s.getMin():" << s.getMin() << endl;
}
cout << "The datum in the stack is:" << endl;
while (!s.empty())
{
cout << s.top() << endl;
s.pop();
}
return 0;
}
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5310127.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/230766
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!