面試題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;
}