一、基本概念

1、栈的定义

栈，Stack，是一种特殊的线性表，只允许在表尾进行插入或删除操作的线性表。因而表尾对于栈具有特殊含义，称为栈顶top，与此对应的表头称为栈底bottom。

栈的操作特性可以概括为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out，FILO）。

2、栈的数学性质

n 个不同元素进栈，出栈元素不同排列的个数为:

该公式称为卡特兰（Catalan）数。

3、栈的基本操作

InitStack(&S)：构造一个空栈或对一个空栈初始化。

Destroyed(&S)：销毁一个栈，释放空间。

ClearStack(&S)：情况栈中的所有元素。

StackEmpty(S)：判断一个栈是否为空栈。

StackLength(S)：获取栈的长度。

GetTop(S)：获取栈顶元素，不修改栈顶指针。

Push(&S,e)：压栈，在栈顶插入一个新的元素，修改栈顶指针，栈长加一。

Pop(&s,&e)：弹栈，从栈顶移除一个元素，修改栈顶指针，栈长减一。

StackTraverse(s)：从栈顶到栈底依次遍历元素并输出到屏幕上。

4、栈的存储结构

栈的存储结构，也就是栈的实现，也有两种方式：顺序栈和链栈。

顺序栈，顾名思义，是采用顺序结构，也就是数组进行描述实现的。

链栈，就是采用链式结构，用指针进行描述实现的。

二、顺序栈C++实现

代码如下：

#pragma once#include 
     
      using namespace std;class SeqStack{
     private:	// 存放元素	int* data;	// 栈顶指针	int top;	// 栈长	int length;	// 最大栈长	int max;public:	// 构造空栈	SeqStack();	// 初始化	bool InitStack(int a[], int len);	// 判空	bool StackEmpty();	// 获取栈长	int StackLength();	// 获取栈顶元素	int getTop();	// 压栈	bool push(int value);	// 弹栈	bool pop(int& e);	// 遍历栈	void StackTraverse();	// 清空栈	bool clear();};SeqStack::SeqStack(){
     	this->data = NULL;	this->top = -1;	this->length = 0;	this->max = 20;}bool SeqStack::InitStack(int a[], int len){
     	try {
     		if (len > this->max)			return false;		this->data = new int[len];		for (int i = 0; i < len; i++)		{
     			this->data[i] = a[i];			this->top++;		}		this->length = len;		return true;	}	catch (exception e) {
     		cout << e.what() << endl;		return false;	}}bool SeqStack::StackEmpty(){
     	if (this->top == -1)		return true;	return false;}int SeqStack::StackLength(){
     	return this->length;}int SeqStack::getTop(){
     	if (this->StackEmpty())		return 0;	return this->data[this->top];}bool SeqStack::push(int value){
     	if (this->top == this->max - 1)	{
     		cout << "栈已满，请先弹栈，再压栈！" << endl;		return false;	}	this->data[length] = value;	top += 1;	length += 1;}bool SeqStack::pop(int& e){
     	if (top == -1)	{
     		cout << "栈已空，无法弹栈" << endl;		return false;	}	e = data[top--];	length -= 1;	return true;}void SeqStack::StackTraverse(){
     	if (this->StackEmpty())	{
     		cout << "空栈！" << endl;		return;	}	for (int i = top; i >= 0; i--)		cout << data[i] << " ";	cout << endl;}bool SeqStack::clear(){
     	if (this->StackEmpty())	{
     		cout << "空栈！" << endl;		return false;	}	top = -1;	length = 0;	return true;}

三、链栈C实现

由于链栈不需要头指针，由限定在栈顶操作，因此采用C语言的 struct 比用 class 容易实现，代码如下：

#pragma once#include 
     
      using namespace std;typedef struct StackNode{
     	int data;	int len;	StackNode* next;}StackNode, * LinkStack;bool create(LinkStack& s){
     	s = NULL;	return true;}bool init(LinkStack& s, int a[], int len){
     	try {
     		LinkStack p;		for (int i = 0; i < len; i++)		{
     			p = new StackNode;			p->data = a[i];			p->next = s;			p->len = i + 1;			s = p;		}		s->len = len;		return true;	}	catch (exception e) {
     		cout << e.what() << endl;		return false;	}}int getTop(LinkStack s){
     	return s->data;}bool push(LinkStack& s, int value){
     	LinkStack p = new StackNode;	p->data = value;	p->next = s;	p->len = s->len + 1;	s = p;	return true;}bool pop(LinkStack& s, int& e){
     	if (s == NULL)	{
     		cout << "栈空" << endl;		return false;	}	e = s->data;	LinkStack p = s;	s = s->next;	delete p;	return true;}void traverse(LinkStack s){
     	LinkStack p = s;	for (int i = 0; i < s->len; i++)	{
     		cout << p->data << " ";		p = p->next;	}	cout << endl;}