1.栈的定义
限定仅在表尾进行插入和删除操作的线性表

栈顶：允许插入和删除的一端（表尾端）称为栈顶
栈底：表头端
栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出(LIFO)的原则

2.顺序栈的实现（附源码）

利用顺序存储结构实现的栈，

代码：


#include
#include

using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100 //顺序栈可使用的最大存储空间

typedef int SElemType;
typedef int Status;

typedef struct {
	SElemType* top;
	SElemType* base;
	int stacksize;
}SqStack;

//顺序栈初始化
Status InitSqStack(SqStack &S) {
	S.base = new SElemType[MAXSIZE];
	if (!S.base) {
		exit(OVERFLOW);
	}
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

//判断顺序栈是否为空
bool SqStackEmpty(SqStack S) {
	if (S.base) {
		return S.top == S.base;
	}
	else {
		return ERROR;
	}
}

//求顺序栈的长度
Status SqStackLength(SqStack S,SElemType &e) {
	if (S.base) {
		e= S.top - S.base;
		return OK;
	}
	else {
		return ERROR;
	}
	
}

//清空顺序栈
Status ClearSqStack(SqStack &S) {
	if (S.base) {	
		S.top = S.base;
		return OK;
	}
	else {
		return ERROR;
	}
}

//销毁顺序栈
Status DestroySqStack(SqStack &S) {
	if (S.base) {
		delete[]S.base;
		S.stacksize = 0;
		S.top = S.base = NULL;
		return OK;
	}
	else {
		return ERROR;
	}
	
}

//入栈
Status Push(SqStack &S,SElemType e) {
	if (S.base) {
		if (S.top - S.base == S.stacksize) {
			return OVERFLOW;
		}
		*S.top++ = e;
		return OK;
	}
	else {
		return ERROR;
	}

}

//出栈
Status Pop(SqStack& S, SElemType& e) {
	if (S.base) {
		if (S.top == S.base) {
			cout << "栈为空，出栈失败！"<>*(S.top)) {
		S.top++;
		if (cin.get() == 'n') {
			break;
		}
		
	}
	cin.clear();
	cin.ignore();
	return OK;
}


int main() {

	cout << "1. 顺序栈初始化" << endl;
	cout << "2. 建栈" << endl;
	cout << "3. 判断顺序栈是否为空" << endl;
	cout << "4. 求顺序栈的长度" << endl;
	cout << "5. 清空顺序栈" << endl;
	cout << "6. 销毁顺序栈" << endl;
	cout << "7. 入栈" << endl;
	cout << "8. 出栈" << endl;
	cout << "9. 取栈顶元素" << endl;
	cout << "10. 输出栈 " << endl;
	cout << "0. 退出" << endl;

	SqStack S;
	int choice=-1;
	SElemType e;

	while (choice!=0) {
		cout << endl << "请选择: ";
		cin >> choice;


		switch (choice) {
		case 1:
			if (InitSqStack(S)) {
				cout << "顺序栈初始化成功！" << endl;
			}
			else {
				cout << "顺序栈初始化失败！" << endl;
			}
			break;

		case 2:
			if (SqStackCreate(S)) {
				cout << "建栈成功！" << endl;
			}
			break;

		case 3:
			if (SqStackEmpty(S)) {
				cout << "顺序栈为空！" << endl;
			}
			else {
				cout << "顺序栈不为空！" << endl;
			}
			break;

		case 4: 

			if (SqStackLength(S,e)) {
				cout << "顺序栈长度为" << e << endl;
			}
			else {
				cout << "顺序栈不存在！" << endl;
			}
			break;

		case 5:
			if (ClearSqStack(S)) {
				cout << "清空成功！" << endl;
			}
			else {
				cout << "清空失败,栈不存在！" << endl;
			}
			break;

		case 6:
			if (DestroySqStack(S)) {
				cout << "销毁成功！" << endl;
			}
			else {
				cout << "销毁失败,栈不存在！" << endl;
			}
			break;

		case 7:
			cout << "请输入插入元素： ";
			cin >> e;
			if (Push(S,e)) {
				cout << "入栈成功！" << endl;
			}
			else {
				cout << "栈不存在！" << endl;
			}
			break;

		case 8:
			if (Pop(S, e)) {
				cout << "出栈成功！" << endl;
			}
			else {
				cout << "栈不存在！" << endl;
			}
			break;

		case 9:
			if (GetTop(S,e)) {
				cout << "栈顶元素为： " << e< 
运行结果： 
 
  
  
 
3.链栈表示和实现（附源码） 
 
 在应用程序无法预先估计栈可能达到的最大容量时，应该使用链栈 
 
表示：运算受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。 
代码： 

#include
#include

using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int SElemType;
typedef int Status;

typedef struct LSNode{
	SElemType data;
	struct LSNode* next;
}LSNode,*LinkStack;

//链栈初始化
Status InitLinkStack(LinkStack& S) {
	S = NULL;
	return OK;
}

//判断链栈是否为空
bool LinkStackEmpty(LinkStack S) {
	return S==NULL;
}

//求链栈的长度
int LinkStackLength(LinkStack S) {
	LSNode* p = S;
	int length = 0;
	while (p) {
		p = p->next;
		length++;
	}
	return length;
}



//销毁链栈
//由于无头节点，销毁和清空、栈不存在和栈空大概算是一个意思吧
Status DestroyLinkStack(LinkStack& S) {
	LSNode* p = S;
	while (p) {
		S = S->next;
		delete p;
		p = S;
	}
	return OK;
}

//入栈
Status Push(LinkStack& S, SElemType e) {
	LSNode* p = new LSNode;
	if (!p) {
		exit(OVERFLOW);
	}
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}

//出栈
Status Pop(LinkStack& S, SElemType& e) {
	if (S) {
		LSNode* p = S;
		e = p->data;
		S = S->next;
		delete p;
		return OK;
	}
	else {
		return ERROR;
	}
}

//取栈顶元素
Status GetTop(LinkStack S, SElemType& e) {
	if (S) {
		e = S->data;
		return OK;
	}
	else {
		return ERROR;
	}
}

//建栈
Status LinkStackCreate(LinkStack& S) {
	cout << "请输入建栈元素(按两次回车键结束）： ";
	LSNode* p = new LSNode;
	while (cin >> p->data) {
		p->next = S;
		S = p;	
		if (cin.get() == 'n') {
			break;
		}
		p = new LSNode;
	}
	cin.clear();
	cin.ignore();
	return OK;
}

//打印栈
void LinkStackPrint(LinkStack S){
	LSNode* p = S;
	SElemType* container = new SElemType[LinkStackLength(S)];
	int counter= LinkStackLength(S)-1;
	while (p) {
		container[counter] = p->data;
		p = p->next;
		counter--;
	}
	for (int i = 0; i < LinkStackLength(S); i++) {
		cout << container[i]<<" ";
	}
	cout << endl;
}


int main() {

	cout << "1. 链栈初始化" << endl;
	cout << "2. 建栈" << endl;
	cout << "3. 判断链栈是否为空" << endl;
	cout << "4. 求链栈的长度" << endl;
	cout << "5. 销毁（清空）链栈" << endl;
	cout << "6. 入栈" << endl;
	cout << "7. 出栈" << endl;
	cout << "8. 取栈顶元素" << endl;
	cout << "9. 输出栈 " << endl;
	cout << "0. 退出" << endl;

	LinkStack S=new LSNode;		//VS里面必须new一下,否则会显示"使用了可能未初始化的本地指针变量S"
	int choice = -1;
	SElemType e=0;

	while (choice != 0) {
		cout << endl << "请选择: ";
		cin >> choice;


		switch (choice) {
		case 1:
			if (InitLinkStack(S)) {
				cout << "链栈初始化成功！" << endl;
			}
			break;

		case 2:
			if (LinkStackCreate(S)) {
				cout << "建栈成功！" << endl;
			}
			break;

		case 3:
			if (LinkStackEmpty(S)) {
				cout << "链栈为空！" << endl;
			}
			else {
				cout << "链栈不为空！" << endl;
			}
			break;

		case 4:
			LinkStackLength(S);
			cout << "链栈长度为" << LinkStackLength(S) << endl;
			break;

		case 5:
			if (DestroyLinkStack(S)) {
				cout << "销毁成功！" << endl;
			}
			break;

		case 6:
			cout << "请输入插入元素： ";
			cin >> e;
			if (Push(S, e)) {
				cout << "入栈成功！" << endl;
			}
			break;

		case 7:
			if (Pop(S, e)) {
				cout << "出栈成功！" << endl;
			}
			else {
				cout << "栈为空！" << endl;
			}
			break;

		case 8:
			if (GetTop(S, e)) {
				cout << "栈顶元素为： " << e << endl;
			}
			else {
				cout << "栈为空！" << endl;
			}
			break;

		case 9:
			LinkStackPrint(S);
			break;

		case 0:
			choice = 0;
			break;

		}
	}
	return 0;

}
 
运行结果如下： 
 
  
 
4.栈与递归 
 
 栈有一个重要应用是实现递归 
 
4.1关于递归 
递归的定义 
若一个对象部分地包含它自己,  或用它自己给自己定义,  则称这个对象是递归的
若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程
以下三种情况常常用到递归方法 
递归定义的数学函数  eg:阶乘函数，2阶Fibonaci数列
具有递归特性的数据结构  eg；链表，树，广义表
可递归求解的问题  eg:Hanoi塔问题，
4.2函数嵌套的调用过程 
 
 当多个函数构成嵌套调用时, 遵循后调用先返回：后调用先返回 
 正好符合栈的后进先出原则 
 
调用前, 系统完成: 
将实参,返回地址等传递给被调用函数
为被调用函数的局部变量分配存储区
将控制转移到被调用函数的入口
调用后, 系统完成: 
保存被调用函数的计算结果
释放被调用函数的数据区
依照被调用函数保存的返回地址将控制转移到调用函数
很容易晓得，上述的信息传递和控制转移必须通过栈来实现 
即系统把整个程序运行所需的数据空间安排在一个栈内，每调用一个函数时，就为他在栈顶分配一个空间，每当从一个函数退出时，释放其存储区，也就是当前运行的函数一定在栈顶！ 
4.3 栈与递归 
一个递归函数的运行过程，类似于多个函数的嵌套调用 
层次： 
 
递归工作站：系统需要设立一个递归工作站来存储每一层递归所需要的信息！ 
 工作记录：每一层递归所需的信息构成一个工作记录，包括所有的实参和局部变量，以及上一层的返回地址，每进入一层递归，产生一个新的工作记录压入栈顶，每退出一层递归，就从栈顶弹出一个工作记录。 
活动记录：当前执行层的工作记录（递归工作栈栈顶的工作记录）

【数据结构详细学习笔记7】栈的定义和实现

1.栈的定义
限定仅在表尾进行插入和删除操作的线性表

栈顶：允许插入和删除的一端（表尾端）称为栈顶
栈底：表头端
栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出(LIFO)的原则

C/C++/C#相关栏目本月热门文章

【数据结构详细学习笔记7】栈的定义和实现

1.栈的定义 限定仅在表尾进行插入和删除操作的线性表 栈顶：允许插入和删除的一端（表尾端）称为栈顶栈底：表头端栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出(LIFO)的原则

4.栈与递归 栈有一个重要应用是实现递归

C/C++/C#相关栏目本月热门文章

1.栈的定义
限定仅在表尾进行插入和删除操作的线性表

栈顶：允许插入和删除的一端（表尾端）称为栈顶
栈底：表头端
栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出(LIFO)的原则

4.栈与递归

栈有一个重要应用是实现递归