CStack.h:
#pragma once class CStackElement
{
public:
CStackElement(void){}
CStackElement(int data, int min=0)
{
m_nData = data;
m_nMin = min;
} ~CStackElement(void){} public:
int m_nData;
int m_nMin;
}; class CStack
{
public:
CStack(int maxSize);//普通构造函数，构造一个大小为maxSize的栈
CStack(const CStack &stack);//拷贝构造函数
CStack & operator=(const CStack &stack);//赋值函数
~CStack(void); void Push(int nPushElement);//向栈中压入一个元素nElement
void Pop();//从栈中弹出一个元素，并返回
int Min();//O(1)的时间返回最小元素值 private:
CStackElement *m_pStackArr;
int m_top;//指向栈顶元素的下一个位置
int m_nMaxSize;
};
CStack.cpp:
#include "StdAfx.h"
#include "CStack.h"
#include <iostream>
using namespace std; //普通构造函数，构造一个大小为maxSize的栈
CStack::CStack(int maxSize)
{
m_top = 0;//指向栈顶元素的下一个位置
m_nMaxSize = maxSize;
m_pStackArr = new CStackElement[m_nMaxSize];
} //拷贝构造函数
CStack::CStack(const CStack &stack)
{
m_top = stack.m_top;
m_nMaxSize = stack.m_nMaxSize;
m_pStackArr = new CStackElement[m_nMaxSize];
memcpy(m_pStackArr, stack.m_pStackArr, m_nMaxSize);
} //赋值函数
CStack & CStack::operator=(const CStack &stack)
{
if (this == &stack)//自赋值检查
{
return *this;
} if (stack.m_top != 0)//stack为空
{
if (m_nMaxSize < stack.m_nMaxSize)
{
m_nMaxSize = stack.m_nMaxSize;
delete [] m_pStackArr;
m_pStackArr = new CStackElement[m_nMaxSize];
memcpy(m_pStackArr, stack.m_pStackArr, m_nMaxSize);
}
}
return *this;
} //向栈中压入一个元素nElement
void CStack::Push(int nPushElement)
{
if (m_top == m_nMaxSize)
{
cout << "栈满！" << endl;
}
else if (m_top == 0)//栈空
{
m_pStackArr[m_top++].m_nData = nPushElement;
m_pStackArr[m_top++].m_nMin = nPushElement;
cout << "压入" << nPushElement<< endl;
}
else
{
if (m_pStackArr[m_top-1].m_nMin > nPushElement)
{
m_pStackArr[m_top].m_nMin = nPushElement;
}
else
{
m_pStackArr[m_top].m_nMin = m_pStackArr[m_top-1].m_nMin;
} m_pStackArr[m_top++].m_nData= nPushElement;
cout << "压入" << nPushElement<< endl;
}
} //从栈中弹出一个元素，并返回
void CStack::Pop()
{
int nPopElement = 0;
if (m_top == 0)
{
nPopElement = -1;
cout << "栈空！" << endl;
}
else
{
nPopElement = m_pStackArr[--m_top].m_nData;
cout << "弹出" << nPopElement << endl;
}
} //O(1)的时间返回最小元素值
int CStack::Min()
{
if (m_top == 0)
{
cout << "栈空！" << endl;
return -1;
}
else
{
return m_pStackArr[m_top-1].m_nMin;
}
} CStack::~CStack(void)
{ }
测试代码：
// 栈和队列的灵活应用一：包含min,max函数的栈.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include "CStack.h"
using namespace std; int _tmain(int argc, _TCHAR* argv[])
{
CStack stack(20);
stack.Push(4);
cout << "Min: " << stack.Min() << endl; stack.Push(5);
cout << "Min: " << stack.Min() << endl; stack.Push(2);
cout << "Min: " << stack.Min() << endl; stack.Pop();
cout << "Min: " << stack.Min() << endl; stack.Push(3);
cout << "Min: " << stack.Min() << endl; system("pause");
return 0;
}