顺序栈和链式栈的实现（c++）

什么是栈

• 栈是线性表的一种，其特点是只能在一端进行插入和删除操作，因此具有先进后出和后进先出的特性。
• 把栈形象一点的说明就是把它比作桶这样一种容器。栈有两端，把允许进行插入和删除的一端作为栈顶，也就是桶口，或者是线性表的表尾；而另一端叫做栈底，也就是桶底，或者是表头。
• 通俗直接一点就是一个人为规定的受限的线性表。我们只能在栈顶进行入栈和出栈操作。
• 在STL标准库中，提供了一个名字为stack的容器，是一个类模板，实现了站的功能.
• 栈有两种存储方式，一种为顺序存储的栈，另一种为链式存储的栈。

栈的顺序存储

• 顺序栈和顺序表是类似的，在入栈和出栈操作只支持栈顶的位置进行操作。

顺序栈的编程实现

#include <iostream>


#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif


using namespace std;

namespace _nmsp1
{
#define InitSize 10   //动态数组的初始尺寸
#define IncSize  5    //当动态数组存满数据后每次扩容所能多保存的数据元素数量

	template <typename T> //T代表数组中元素的类型
	class SeqStack
	{
	public:
		SeqStack(int length = InitSize);     //构造函数，参数可以有默认值
		~SeqStack();                         //析构函数

	public:
		bool Push(const T& e);               //入栈（增加数据）		
		bool Pop(T& e);                      //出栈（删除数据），也就是删除栈顶数据
		bool GetTop(T& e);                   //读取栈顶元素，但该元素并没有出栈而是依旧在栈中


		void DispList();                     //输出顺序栈中的所有元素
		int  ListLength();                   //获取顺序栈的长度（实际拥有的元素数量）

		void IncreaseSize();                 //当顺序栈存满数据后可以调用此函数为顺序栈扩容

		bool IsEmpty();                      //判断顺序栈是否为空
		bool IsFull();                       //判断顺序栈是否已满

	private:
		T* m_data;                          //存放顺序栈中的元素		
		int m_maxsize;                       //动态数组最大容量
		int m_top;                           //栈顶指针(用作数组下标)，指向栈顶元素，该值为-1表示空栈
	};

	//通过构造函数对顺序栈进行初始化
	template <typename T>
	SeqStack<T>::SeqStack(int length)
	{
		m_data = new T[length];  //为一维数组动态分配内存		
		m_maxsize = length;      //顺序栈最多可以存储m_maxsize个数据元素
		m_top = -1;              //空栈
	}

	//通过析构函数对顺序栈进行资源释放
	template <typename T>
	SeqStack<T>::~SeqStack()
	{
		delete[] m_data;
	}

	//入栈（增加数据）
	template <typename T>
	bool SeqStack<T>::Push(const T& e)
	{
		if (IsFull() == true)
		{
			//cout << "顺序栈已满，不能再进行入栈操作了!" << endl;
			//return false;
			IncreaseSize(); //扩容
		}

		m_top++;           //栈顶指针向后走
		m_data[m_top] = e; //本行和上一行可以合并写成一行代码：m_data[++m_top] = e;
		return true;
	}

	//当顺序栈存满数据后可以调用此函数为顺序栈扩容，时间复杂度为O(n)
	template<class T>
	void SeqStack<T>::IncreaseSize()
	{
		T* p = m_data;
		m_data = new T[m_maxsize + IncSize]; //重新为顺序栈分配更大的内存空间	
		for (int i = 0; i <= m_top; i++)
		{
			m_data[i] = p[i];                //将数据复制到新区域
		}
		m_maxsize = m_maxsize + IncSize;     //顺序栈最大长度增加IncSize
		delete[] p;                          //释放原来的内存空间
	}

	//出栈（删除数据），也就是删除栈顶数据
	template <typename T>
	bool SeqStack<T>::Pop(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "当前顺序栈为空，不能进行出栈操作!" << endl;
			return false;
		}

		e = m_data[m_top];  //栈顶元素值返回到e中。
		m_top--;           
		return true;
	}

	//读取栈顶元素，但该元素并没有出栈而是依旧在栈顶中，因此m_top值不会发生改变
	template <typename T>
	bool SeqStack<T>::GetTop(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "当前顺序栈为空，不能读取栈顶元素!" << endl;
			return false;
		}

		e = m_data[m_top];  //栈顶元素返回到e中。
		return true;
	}

	//输出顺序栈中的所有元素，时间复杂度为O(n)
	template<class T>
	void SeqStack<T>::DispList()
	{
		//按照从栈顶到栈底的顺序来显示数据
		for (int i = m_top; i >= 0; --i)
		{
			cout << m_data[i] << " ";  //每个数据之间以空格分隔
		}
		cout << endl; //换行
	}

	//获取顺序栈的长度（实际拥有的元素数量），时间复杂度为O(1)
	template<class T>
	int SeqStack<T>::ListLength()
	{
		return m_top + 1;
	}

	//判断顺序栈是否为空，时间复杂度为O(1)
	template<class T>
	bool SeqStack<T>::IsEmpty()
	{
		if (m_top == -1)
		{
			return true;
		}
		return false;
	}

	//判断顺序栈是否已满，时间复杂度为O(1)
	template<class T>
	bool SeqStack<T>::IsFull()
	{
		if (m_top >= m_maxsize - 1)
		{
			return true;
		}
		return false;
	}
int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	_nmsp1::SeqStack<int> seqobj(10);
	seqobj.Push(150);
	seqobj.Push(200);
	seqobj.Push(300);
	seqobj.Push(400);
	seqobj.DispList();
	int eval = 0;
	seqobj.Pop(eval);
	seqobj.Pop(eval);
	cout << "---------" << endl;
	seqobj.DispList();
	seqobj.Push(8100);
}

---

共享栈

• 根据以上顺序栈的实现来看，顺序栈一个比较大的缺点是保存数据的空间初始尺寸不好确定，太大造成浪费，太小造成频繁扩容操作，消耗性能；
• 共享栈的含义：开辟一块保存数据的空间，让这两个栈同时使用这一块空间，也许能达到最大限度地利用这块空间，减少浪费的目的。
• 共享栈的入栈和出栈的如图所示

• 代码实现只写出了与顺序栈的不一样的地方

//共享栈
	template <typename T> //T代表数组中元素的类型
	class ShareStack
	{
	public:
		ShareStack(int length = InitSize)    //构造函数，参数可以有默认值
		{
			m_data = new T[length];  //为一维数组动态分配内存
			m_maxsize = length;      //顺序栈最多可以存储m_maxsize个数据元素
			m_top1 = -1;             //顺序栈1的栈顶指针为-1，表示空栈
			m_top2 = length;         //顺序栈2的栈顶指针为length，表示空栈
		}
		~ShareStack()                        //析构函数
		{
			delete[] m_data;
		}

	public:
		bool IsFull()                        //判断共享栈是否已满
		{
			if (m_top1 + 1 == m_top2)
			{
				return true;
			}
			return false;
		}

		bool Push(int stackNum, const T& e)      //入栈（增加数据）,参数stackNum用													//于标识栈1还是栈2
		{
			if (IsFull() == true)
			{
				//共享栈满了，读者也可以自行增加代码来支持动态增加共享栈的容量，这里简单处					//理，直接返回false
				cout << "共享栈已满，不能再进行入栈操作了!" << endl;
				return false;
			}
			if (stackNum == 1)
			{
				//要入的是顺序栈1
				m_top1++;           //栈顶指针向后走
				m_data[m_top1] = e;
			}
			else
			{
				//要入的是顺序栈2
				m_top2--;
				m_data[m_top2] = e;
			}
			return true;
		}

		bool Pop(int stackNum, T& e)          //出栈（删除数据），也就是删除栈顶数据
		{
			if (stackNum == 1)
			{
				//要从顺序栈1出栈
				if (m_top1 == -1)
				{
					cout << "当前顺序栈1为空，不能进行出栈操作!" << endl;
					return false;
				}
				e = m_data[m_top1];  //栈顶元素值返回到e中
				m_top1--;
			}
			else
			{
				//要从顺序栈2出栈
				if (m_top2 == m_maxsize)
				{
					cout << "当前顺序栈2为空，不能进行出栈操作!" << endl;
					return false;
				}
				e = m_data[m_top2];
				m_top2++;
			}
			return true;
		}

	private:
		T* m_data;                          //存放共享栈中的元素
		int m_maxsize;                       //动态数组最大容量
		int m_top1;                          //顺序栈1的栈顶指针
		int m_top2;                          //顺序栈2的栈顶指针    
	};

---

栈的链式存储

• 表明含义就是用链式存储方式来实现的栈，顾名思义就是受限的单链表，只不过是人为的规定在单链表的第一个位置进行入栈和出栈操作。
• 需要注意的是链表头是栈顶，不要搞混了。因为要考虑到只在链表头位置插入数据，以下的编程实现没有头结点。

#include <iostream>

#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif


using namespace std;
namespace _nmsp1
{
	template <typename T>
	struct StackNode
	{
		T data;
		StackNode<T>* next;
	};

	template <typename T>
	class LinkStack
	{
	public:

		LinkStack();
		~LinkStack();
	public:
		bool Push(const T& e);
		bool Pop(T& e);
		bool GetTop(T& e);

		void DisList();
		int ListLength();
		bool Empty();
	private:
		StackNode<T>* m_top;
		int  m_length;
	};


	//构造函数
	template<typename T>
	LinkStack<T>::LinkStack()
	{
		m_top = nullptr;
		m_length = 0;
	}

	//入栈操作
	template<typename T>
	bool LinkStack<T>::Push(const T& e)
	{
		StackNode<T>* node = new StackNode<T>;
		node->data = e;
		node->next = m_top;
		m_top = node;
		m_length++;
		return true;
	}
	//出栈操作
	template<typename T>
	bool LinkStack<T>::Pop(T& e)
	{
		if (Empty() == true)
		{
			return false;
		}
		StackNode<T>* p_willdel = m_top;  //和单链表是一样的操作
		m_top = m_top->next;
		m_length--;
		e = p_willdel->data;
		delete p_willdel;
		return true;
	}

	template<typename T>
	bool LinkStack<T>::GetTop(T& e)
	{
		if (Empty() == true)
		{
			return false;

		}
		e = m_top->data;
		return true;
	}

	template <class T>
	void LinkStack<T>::DisList()
	{
		if (Empty() == true)
		{
			return;
		}

		StackNode<T>* p = m_top;
		while (p != nullptr)
		{
			cout << p->data << " ";
			p = p->next;
		}
		cout << endl;
	}

	template<typename T>
	int LinkStack<T>::ListLength()
	{
		return m_length;
	}

	//判断链式栈是否为空，时间复杂度为O(1)
	template<class T>
	bool LinkStack<T>::Empty()
	{
		if (m_top == nullptr) //链式栈为空
		{
			return true;
		}
		return false;
	}

	//通过析构函数对链式栈进行资源释放
	template <typename T>
	LinkStack<T>::~LinkStack()
	{
		T tmpnousevalue = { 0 };
		while (Pop(tmpnousevalue) == true) {}//Pop具有删除的元素的能力，真正退出												//while循环的是Empty（）得到的false
	}
}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	_nmsp1::LinkStack<int> slinkobj;
	slinkobj.Push(12);
	slinkobj.Push(24);
	slinkobj.Push(48);
	slinkobj.Push(100);
	slinkobj.DisList();

	int eval = 0;
	slinkobj.Pop(eval);
	slinkobj.DisList();

	return 0;
}

---

两者的对比

• 与顺序栈相比，链式栈式没有长度限制，不存在浪费空间的问题
• 对于入栈和出栈这些需要对数据进行定位的操作，顺序栈更加方便
• 链式栈需要额外的指针域来指向下一个数据结点，会略微降低数据的存储效率
• 如果数据无法提前预估，一般考虑链式栈，知道数量固定，考虑使用顺序栈

---

应用

1. 保存临时数据
2. 计算机表达式结果

利用栈进行括号的检验

• 需求说明：利用栈来检查一个表达式中括号数量是否匹配。（）[] {}假设这三种括号，目的就是给出一个含有三种括号的表达式，来检查这个表达式的合法性。
• 思路：
  • 从左侧开始扫描表达式，遇到（ [ { 这三种左括号之一将其入栈。
  • 当遇到 ) ] } 之一时，就从栈顶取出一个括号进行尝试匹配。
  • 如果匹配成功，则继续扫描表达式剩余的字符串，如果匹配失败，或者栈顶取出的数据失败都判定为表达式不正确。
  • 当表达式子的所有括号扫描完毕并且括号匹配之后，还要确定栈是否为空，栈为空，则说明表达式格式合法，否则为非法。

#include <iostream>

#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

//#include <boost/type_index.hpp>
using namespace std;
//#pragma warning(disable : 4996) 

namespace _nmsp1
{
	//链式栈中每个节点的定义
	template <typename T> //T代表数据元素的类型
	struct StackNode
	{
		T        data;  //数据域，存放数据元素
		StackNode<T>* next;  //指针域，指向下一个同类型（和本节点类型相同）节点
	};

	//链式栈的定义
	template <typename T>
	class LinkStack
	{
	public:
		LinkStack();      //构造函数，参数可以有默认值
		~LinkStack();     //析构函数

	public:
		bool Push(const T& e); //入栈元素e
		bool Pop(T& e);        //出栈（删除数据），也就是删除栈顶数据
		bool GetTop(T& e);     //读取栈顶元素，但该元素并没有出栈而是依旧在栈中

		void DispList();                     //输出链式栈中的所有元素
		int  ListLength();                   //获取链式栈的长度
		bool Empty();                        //判断链式栈是否为空

	private:
		StackNode<T>*     m_top;   //栈顶指针
		int               m_length;//链式栈当前长度
	};

	//通过构造函数对链式栈进行初始化
	template <typename T>
	LinkStack<T>::LinkStack()
	{
		m_top = nullptr;
		m_length = 0;
	}

	//入栈元素e，时间复杂度为O(1)
	template <typename T>
	bool LinkStack<T>::Push(const T& e)
	{
		StackNode<T>* node = new StackNode<T>;
		node->data = e;
		node->next = m_top;
		m_top = node;
		m_length++;
		return true;
	}

	//出栈（删除数据），也就是删除栈顶数据，时间复杂度为O(1)
	template <typename T>
	bool LinkStack<T>::Pop(T& e)
	{
		if (Empty() == true) //链式栈为空
			return false;

		StackNode<T>* p_willdel = m_top;
		m_top = m_top->next;
		m_length--;
		e = p_willdel->data;
		delete p_willdel;
		return true;
	}

	//读取栈顶元素，但该元素并没有出栈而是依旧在栈中
	template <typename T>
	bool LinkStack<T>::GetTop(T& e)
	{
		if (Empty() == true) //链式栈为空
			return false;

		e = m_top->data;
		return true;
	}

	//输出链式栈中的所有元素，时间复杂度为O(n)
	template<class T>
	void LinkStack<T>::DispList()
	{
		if (Empty() == true) //链式栈为空
			return;

		StackNode<T>* p = m_top;
		while (p != nullptr)
		{
			cout << p->data << " ";  //每个数据之间以空格分隔
			p = p->next;
		}
		cout << endl; //换行
	}

	//获取链式栈的长度，时间复杂度为O(1)
	template<class T>
	int  LinkStack<T>::ListLength()
	{
		return m_length;
	}

	//判断链式栈是否为空，时间复杂度为O(1)
	template<class T>
	bool LinkStack<T>::Empty()
	{
		if (m_top == nullptr) //链式栈为空
		{
			return true;
		}
		return false;
	}

	//通过析构函数对链式栈进行资源释放
	template <typename T>
	LinkStack<T>::~LinkStack()
	{
		T tmpnousevalue = {0};
		while (Pop(tmpnousevalue) == true) {}//把栈顶元素删光，实际上式通过empty来决											//定是否退出循环，此时也就是空栈了				
	}
}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);


	bool ifMatchSucc = true;  //是否匹配成功的标志，先标记未匹配成功
	_nmsp1::LinkStack<char> slinkobjprocKH;  //保存左括号的栈
	string strExp = "[({}){}]";
	for (size_t i = 0; i < strExp.size(); ++i)
	{
		if (strExp[i] ==  '(' ||  strExp[i]  == '[' || strExp[i] == '{') //左括																	//号全部入栈
		{
			slinkobjprocKH.Push(strExp[i]);
		}
		else
		{
			//当前是一个右括号，则从栈顶取出一个左括号
			char tmptopchar;
			if (slinkobjprocKH.Pop(tmptopchar) == false) //从栈顶取出数据失败
			{
				ifMatchSucc = false; //匹配失败标记
				break; //跳出for循环
			}

			//取得了栈顶的一个左括号，看一看是否匹配
			if (
				(strExp[i] == ')' && tmptopchar == '(') ||
				(strExp[i] == ']' && tmptopchar == '[') ||
				(strExp[i] == '}' && tmptopchar == '{')
				)
			{
				continue; //继续扫描
			}
			else
			{
				//括号不匹配
				ifMatchSucc = false; //匹配失败标记
				break; //跳出for循环
			}
		}
	}// end for

	//扫描完成后，还要确定slinkobjprocKH为空才可以
	if (ifMatchSucc == true && slinkobjprocKH.Empty()==false)
	{
		ifMatchSucc = false;
	}

	if (ifMatchSucc == true)
	{
		cout << "\"" << strExp << "\"格式合法，括号配对数量和顺序都正确" << endl;
	}
	else
	{
		cout << "\"" << strExp << "\"格式非法，括号配对数量或顺序不正确" << endl;
	}	
	return 0;
}