本课程将带领大家体会栈这种数据结构的美妙，并详细讲解从单一数据类型栈到栈模板的升华过程，最后安排数制转换及括号匹配的例子，使学员可以通过例子对栈的知识有更深刻的理解和认识，所有知识均通过编码实践的方式讲解到操作层面，力求即学即会。

1 栈的工作原理

后进先出(LIFO, last in first out )

2 单一数据类型栈

#include <iostream>
using namespace std;

class MyStack
{
public:
	MyStack(int size); // 分配内存初始化栈空间，设定栈容量，指定栈顶
	~MyStack(); // 回收栈空间内存
	bool stackEmpty(); // 判空
	bool stackFull(); // 判满
	void clearStack(); // 清空栈
	int stackLength(); // 已有元素数量
	bool push(char elem); // 元素入栈，栈顶下降
	bool pop(char &elem); // 元素出栈，栈顶下降
	void stackTraverse(bool isFromBottom); // 遍历栈
private:
	char *m_pBuffer; // 栈空间指针
	int m_iSize; // 栈容量
	int m_iTop; // 栈顶位置下标(栈底下标为0)
};

int main(void)
{
	// 创建栈实例
	MyStack *pStack = new MyStack(5);

	// 判空
	if(pStack->stackEmpty())
	{
		cout << "栈为空" << endl;
	}

	// 入栈
	pStack->push('a'); // 底
	pStack->push('b');
	pStack->push('c');
	pStack->push('d');
	pStack->push('e'); // 顶

	// 栈长度
	cout << pStack->stackLength() << endl;


	// 判满
	if(pStack->stackFull())
	{
		cout << "栈为满" << endl;
	}

	// 出栈
	char elem = 0;
	pStack->pop(elem);
	cout << elem << endl;

	// 遍历
	pStack->stackTraverse(true);

	delete pStack;
	pStack = NULL;
	return 0;
}

// 构造器（初始化）
MyStack::MyStack(int size)
{
	m_iSize = size;
	m_pBuffer = new char[m_iSize];
	m_iTop = 0;
}

// 释放内存
MyStack::~MyStack()
{
	delete []m_pBuffer;
	m_pBuffer = NULL;
}

// 判空
bool MyStack::stackEmpty()
{
	return m_iTop == 0 ? true : false;
}

// 栈满
bool MyStack::stackFull()
{
	return m_iTop == m_iSize ? true : false;
}

// 清空栈
void MyStack::clearStack()
{
	m_iTop = 0;
}

// 获取栈的大小
int MyStack::stackLength()
{
	return m_iTop;
}

// 入栈
bool MyStack::push(char elem)
{
	if(stackFull())
	{
		return false; 
	}
	else
	{
		m_pBuffer[m_iTop] = elem;
		m_iTop++;
		return true;
	}
}

// 出栈
bool MyStack::pop(char &elem)
{
	if(stackEmpty())
	{
		return false;
	}
	else
	{
		m_iTop--;
		elem = m_pBuffer[m_iTop];
		return true;
	}
}

// 遍历
void MyStack::stackTraverse(bool isFromBottom)
{
	if (isFromBottom)
	{
		for(int i = 0; i < m_iTop; i++)
		{
			cout << m_pBuffer[i] << endl;
		}
	}
	else
	{
		for(int i = m_iTop - 1; i >= 0; i--)
		{
			cout << m_pBuffer[i] << endl;
		}
	}
}

3 栈模版

说明： 将普通栈改为类模版栈，使其可以适用于任何数据类型。

类模版定义和实现需要写在同一个文件中，因为有些编译器不支持分开写。
需要考虑栈元素为复杂的自定义类型的情况，比如是否需要定义拷贝构造函数等。
使用该栈模版的类型需要重载 << 运算符。

MyStack.h

#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
template <typename T>
class MyStack
{
public:
	MyStack(int size); // 分配内存初始化栈空间，设定栈容量，指定栈顶
	~MyStack(); // 回收栈空间内存
	bool stackEmpty(); // 判空
	bool stackFull(); // 判满
	void clearStack(); // 清空栈
	int stackLength(); // 已有元素数量
	bool push(T elem); // 元素入栈，栈顶下降
	bool pop(T &elem); // 元素出栈，栈顶下降
	void stackTraverse(bool isFromBottom); // 遍历栈
private:
	T *m_pBuffer; // 栈空间指针
	int m_iSize; // 栈容量
	int m_iTop; // 栈顶位置下标(栈底下标为0)
};

// 构造器（初始化）
template <typename T>
MyStack<T>::MyStack(int size)
{
	m_iSize = size;
	m_pBuffer = new T[m_iSize];
	m_iTop = 0;
}

// 释放内存
template <typename T>
MyStack<T>::~MyStack()
{
	delete []m_pBuffer;
	m_pBuffer = NULL;
}

// 判空
template <typename T>
bool MyStack<T>::stackEmpty()
{
	return m_iTop == 0 ? true : false;
}

// 栈满
template <typename T>
bool MyStack<T>::stackFull()
{
	return m_iTop == m_iSize ? true : false;
}

// 清空栈
template <typename T>
void MyStack<T>::clearStack()
{
	m_iTop = 0;
}

// 获取栈的大小
template <typename T>
int MyStack<T>::stackLength()
{
	return m_iTop;
}

// 入栈
template <typename T>
bool MyStack<T>::push(T elem)
{
	if(stackFull())
	{
		return false; 
	}
	else
	{
		m_pBuffer[m_iTop] = elem; // 如果 T 的数据成员有指针等情况，则需要考虑定义拷贝构造函数中
		m_iTop++;
		return true;
	}
}

// 出栈
template <typename T>
bool MyStack<T>::pop(T &elem)
{
	if(stackEmpty())
	{
		return false;
	}
	else
	{
		m_iTop--;
		elem = m_pBuffer[m_iTop];
		return true;
	}
}

// 遍历
template <typename T>
void MyStack<T>::stackTraverse(bool isFromBottom)
{
	if (isFromBottom)
	{
		for(int i = 0; i < m_iTop; i++)
		{
			cout << m_pBuffer[i];
		}
	}
	else
	{
		for(int i = m_iTop - 1; i >= 0; i--)
		{
			cout << m_pBuffer[i];
		}
	}
}

#endif

main.cpp

#include <iostream>
#include "MyStack.h"
using namespace std;

int main(void)
{
	// 创建栈实例
	MyStack<char> *pStack = new MyStack<char>(5);
	...
}

4 栈应用

4.1 进制转换

描述： 输入任意的十进制正整数 N ，分别输出该整数 N 的二进制、八进制、十六进制的数。
公式： N = (N div d) * d + N mod d (div表示整除， mod 表示求余)

1348（十进制）= 2504（八进制）= 544（十六进制） = 10101000100（二进制）

短除法计算过程： 以 1348 为例，分别转化为 8 进制和 16 进制

#include <iostream>
#include "MyStack.h"
using namespace std;

#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main(void)
{
	char num[] = "0123456789ABCDE";
	MyStack<int> *pStack = new MyStack<int>(30); // 栈必须足够大

	// 使用短除法将十进制转换为十六进制
	int N = 2017;
	int mod = 0;
	while(N != 0)
	{
		mod = N % HEXADECIMAL;
		pStack->push(mod); // 栈中16进制的 A ~ E 部分还是用的十进制表示的
		N = N / HEXADECIMAL;
	}

	// 需要转换为16进制表示方式
	int elem = 0;
	while(!pStack->stackEmpty())
	{
		pStack->pop(elem);
		cout << num[elem];
	}

	delete pStack;
	pStack = NULL;

	return 0;
}

4.2 括号匹配

描述：任意输入一组括号，可以判断括号是否匹配。
示例：

[()] 正确
[()()] 正确
[()[()]] 正确
[[()] 错误
[[()]]] 错误

#include <iostream>
#include "MyStack.h"
using namespace std;

int main(void)
{
	MyStack<char> *pStack = new MyStack<char>(30);
	MyStack<char> *pNeedStack = new MyStack<char>(30);

	char str[] = "[()([()()()])]";
	char currentNeed = 0;

	for(int i = 0; i < strlen(str); i++)
	{
		cout << i << endl;
		if(str[i] == currentNeed)
		{
			char elem;
			pStack->pop(elem);

			// 需要匹配的都匹配尽了，则将 currentNeed 置为 0，后面还有就是多余的
			if(!pNeedStack->pop(currentNeed))
			{
				currentNeed = 0;
			}
		}
		else
		{
			pStack->push(str[i]);
			switch(str[i])
			{
				case '[':
					// 如果当前有字符在期待匹配之前出现的字符，就将它入栈
					if(0 != currentNeed)
					{
						pNeedStack->push(currentNeed);
					}
					currentNeed = ']';
					break;
				case '(':
					if(0 != currentNeed)
					{
						pNeedStack->push(currentNeed);
					}
					currentNeed = ')';
					break;
				default:
					cout << "括号不匹配" << endl;
					return 0;
			}
		}
	}
	if(pStack->stackEmpty())
	{
		cout << "括号匹配" << endl;
	}
	else
	{
		cout << "括号不匹配" << endl;
	}

	delete pStack;
	pStack = NULL;
	delete pNeedStack;
	pNeedStack = NULL;

	return 0;
}