栈
栈的定义和基本操作
栈的定义
栈(stack)是限定仅在表尾进行插入和删除操作的线性表
我们把允许插入和删除的一端称为栈顶(top),另一端称为(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
注意:栈是一个线性表。也就是说栈是具有线性关系的，拥有它自己的直接前驱和直接后继。只是，栈是一种特殊的线性表，只能在表尾进行插入和删除操作，这里的表尾通常也被叫做栈顶(top)
栈的基本操作
栈的插入操作（push），叫做进栈，也称压栈、入栈。类似于将子弹压入弹夹
栈的删除操作（pop），叫做出栈，有的也叫做弹栈。如同将弹夹中的子弹取出
进栈示意图：
出栈示意图：
栈的存储和实现
栈数组实现——算法竞赛必备
栈在算法竞赛中也算是常客了。只是使用它的时候需要注意，我们是用数组模拟栈的思想来实现栈。那，为什么要用数组了？我们平时学的都是结构体+指针实现的呀~
就笔者自己使用的C++而言，因为一般竞赛中的测试数据都要拉到极致，比如十万、一百万，假如使用结构体的方式，在new这十万、一百万的空间的时候，可能就超时了。包括下文的队列也是同样的道理，在竞赛中，建议用数组模拟。结构体加指针的玩法，笔者盲猜是用在工程中优化代码效率的
只是C++选手也可以偷偷懒，直接调用C++标准库中提供的库函数
下面就从一道例题来引入怎么用数组快速的模拟栈吧~
例题描述：
原题传送门
参考代码(C++版本)
#include <iostream> using namespace std; const int N = 100010; int m; int stk[N]; //用于模拟栈的数组 int tt; //尾指针 int main() { cin >> m; while (m -- ) { string op; int x; cin >> op; if (op == "push") { cin >> x; stk[ ++ tt] = x; //尾指针向后移动，实现进栈 } else if (op == "pop") tt -- ; // 尾指针向前移动，剔除数组末尾元素，实现出栈 else if (op == "empty") cout << (tt ? "NO" : "YES") << endl; else cout << stk[tt] << endl; } return 0; }
进栈(push)
数组模拟的栈，进栈代码很简单，只有一行…
stk[ ++ tt] = x; //尾指针向后移动，实现进栈
操作的原理图如下：
出栈(pop)
出栈操作就更短了~
else if (op == "pop") tt -- ; // 尾指针向前移动，剔除数组末尾元素，实现出栈
获取信息——栈顶元素和栈是否为空
获取栈顶元素也就是获取尾指针tt所指的空间中的信息，因为是数组模拟的，所以直接将tt放到数组里面
else cout << stk[tt] << endl;
判断栈是不是空栈是通过数组下标实现的。假如现在尾指针tt在栈底(索引为0)的位置，这个栈就是空栈。对于这道题而言,取巧用了三元运算符
else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
栈的链式存储结构及实现——工程开发和期末应试必备
下面的内容了，是数据结构用在工程上和期末考试的卷子上的
栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针Top应该在链表的哪头？
假如按照正常逻辑，放在链表的尾部，插入操作要从头结点开始，挨着挨着遍历过去，到最后一个元素，也就是栈顶就可以实现插入。
删除操作了？删除操作其实是没有办法进行的，因为链表的删除要知道被删除结点的前一个结点的信息，我们没法从链表的尾结点倒着回去找它的前一个结点，也没有办法确定它的前一个结点的信息，因此删除操作就无法实现。
因此经过前人的总结，将头指针所指的位置当做栈顶对于插入和删除操作都十分方便
链栈类型定义
和单链表相同，定义一个结点类型，类型中的成员变量是数据域和指针域
typedef int Datatype; typedef struct stacknode{ Datatype data; //数据域 struct stacknode* next; //指针域 }LinkStack;
初始化栈
首先创建一个链栈S，然后通过NULL将这个创建的栈清空。返回被清空后的链栈的地址信息
参考实现代码：
LinkStack* InitStack() { LinkStack* S; S = NULL; return S; }
判断栈空
判断一个栈是否为空，若栈为空，则返回1，否则返回0
参考实现代码：
int EmptyStack(LinkStack* S) { if(S == NULL) return 1; else return 0; }
进栈
实现流程：
①将新插入的结点p的指针域指向原栈顶S
②将栈顶S指向新结点p
参考实现代码：
LinkStack* push(LinkStack *S,Datatype x) { LinkStack* p; p = (LinkStack*)malloc(sizeof(struct stacknode)); //生成新结点 p->data = x; //将x放到新结点的数据域 p->next = S; //将新结点插入链表的表头之前 S = p; //让头指针执行这个新插入的p。可以理解为让top指针指向这个新插入的结点 return S; //返回栈顶S }
出栈
①p指针指向原栈顶S
② 栈顶S指向其下一个结点
③释放p指针所指的空间
参考实现代码
LinkStack* pop(LinkStack* S , Datatype *x) { LinkStack* p; if(EmptyStack(S)) //先判断栈是否为空栈 { printf("栈为空\n"); return NULL; }else { *x = S->data; //栈顶元素取出来赋值给x p = S; //p指针指向原本的栈顶S S = S->next; //原栈顶S指向下一个结点 free(p); //释放原栈顶空间 return S; //返回栈顶S } }
链栈的两个核心操作入栈push 和 出栈pop 就没有啦，相信小伙伴已经明白是这么一回事了。下面的获取栈顶元素和输出栈中内容就相对轻松很多
取栈顶元素
参考实现代码：
int GetTop(LinkStack* S,Datatype *x) { if(EmptyStack(S)) //先判断栈是否为空 { printf("栈为空\n"); return 0; }else { *x = S->data; //栈顶元素赋值给变量x return 1; } }
显示栈内元素
参考实现代码
void ShowStack(LinkStack *S) { LinkStack *p = S; if(p == NULL) { printf("栈为空\n"); }else { printf("从栈顶起，各元素依次为：\n"); while(p != NULL) { printf("%d\t",p->data); p = p->next; } } }
栈的应用举例
"进制转换"领域
以十进制转二进制为例，操作的流程是每次模2取得余数，整数自身除以权重2，从而更新整数自己。
可以考虑是将余数放到数组里，用一个循环反转数组，再用一个循环将新的数组遍历输出，听起来其实还是蛮麻烦的
实现流程：
用一个循环处理传入的十进制整数x，将它和2取余的结果入栈
用一个循环输出栈中的内容
参考实现代码
//十进制转二进制 void D_B(LinkStack *S,Datatype x) { while(x) //让余数入栈 { S = push(S,x % 2); x /= 2; } printf("转换后的二进制为："); while(!EmptyStack(S)) { S = pop(S,&x); //依次从栈中弹出每一个余数 printf("%d",x); //输入每个余数 } }
