面试题19：包含min函数的栈

#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;
};

#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;
}

补充：软件开发 , C++ ,

上一个：面试题20：栈的压入、弹出序列
下一个：面试题18：顺时针打印矩阵