一.栈的定义
抛开算法，栈在字典中解释为"储存货物或供旅客住宿的房屋",可引申为仓库、中转站，例如我们现在生活中的酒店，在古时候叫客栈，供旅客休息的地方，旅客可以边客栈休息.,休息完毕就离开客栈。
文章图片
我们把生活中的栈类比到计算机中，可以猜想栈是供数据休息(即存储数据)的地方。事实上这么说也是正确的，数据既可以进栈，也可以出栈。栈是一种先进后出(FILO)的数据结构，是一种只能在一端进行加入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数封在栈顶，需要读数据的时候从栈顶开始（最后一个数被第一个读出来) 。
实际上，栈某种意义上讲，它像是一个开口的盒子，先放进去的东西总是会被后放进去的东西压在下面，那么如果想拿出被压住的东西，必须要先取出顶部的东西，也就是后放进去的东西。换个说法就是先入后出。
文章图片
我们称数据进入栈的操作叫压栈，数据从栈中出去的操作叫弹栈。如果有n个元素进栈，出栈元素排序的方法为 
文章图片
种，以上公式称为卡特兰数(Catalan number , 1838年)，会用就可以了。
二.栈的顺序存储实现:(数据结构版)(代码很长，注释很仔细)(不知道自己咋肝出来的）
#include
#include #define MAXSIZE 10// 顺序栈的最大长度。typedef int ElemType;
// 自定义顺序栈的数据元素为整数。typedef struct
{
ElemType data[MAXSIZE];
// 用数组存储顺序栈中的元素。
int top;
// 栈顶指针，从0到MAXSIZE-1，-1表示空栈。
// 也可以从1到MAXSIZE，0表示空栈。
}SeqStack,*PSeqStack;
// 顺序栈SS的初始化操作。
void InitStack(PSeqStack SS);
// 销毁顺序栈SS。
void DestroyStack(PSeqStack SS);
// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee);
// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee);
// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS);
// 清空顺序栈。
void Clear(PSeqStack SS);
// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS);
// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS);
// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS);
// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee);
int main()
{
SeqStack SS;
// 创建顺序栈。InitStack(&SS);
// 初始化顺序栈。printf("栈的长度是%d\n",Length(&SS));
ElemType ee;
// 创建一个数据元素。printf("元素（1、2、3、4、5、6、7、8、9、10）入栈。\n");
ee=1;
Push(&SS, &ee);
ee=2;
Push(&SS, &ee);
ee=3;
Push(&SS, &ee);
ee=4;
Push(&SS, &ee);
ee=5;
Push(&SS, &ee);
ee=6;
Push(&SS, &ee);
ee=7;
Push(&SS, &ee);
ee=8;
Push(&SS, &ee);
ee=9;
Push(&SS, &ee);
ee=10;
Push(&SS, &ee);
printf("栈的长度是%d\n",Length(&SS));
// 只查看栈顶元素的值，元素不出栈。
if (GetTop(&SS,&ee)==1)printf("栈顶的元素值为%d\n",ee);
PrintStack(&SS);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee);
return 0;
}// 初始化顺序栈
void InitStack(PSeqStack SS)
{
Clear(SS);
// 清空顺序栈。
}// 清空顺序栈。
void Clear(PSeqStack SS)
{
if (SS == NULL) return;
// 检查空指针。SS->top=-1;
// 栈顶指针置为-1。
memset(SS->data,0,sizeof(ElemType)*MAXSIZE);
// 数组元素清零。
}// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS)
{
if (SS == NULL) return 0;
// 检查空指针。return SS->top+1;
}// 销毁顺序栈SS。
void DestroyStack(PSeqStack SS)
{
// 静态顺序栈无需释放内存，不需要销毁操作。Clear(SS);
// 清空顺序栈。return;
}// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS)
{
if (SS == NULL) return 0;
// 检查空指针。if (SS->top == -1) return 1;
return 0;
}// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS)
{
if (SS == NULL) return 0;
// 检查空指针。if (SS->top >= MAXSIZE-1) return 1;
return 0;
}// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0;
// 检查空指针。if (IsFull(SS) == 1)
{
printf("顺序栈已满，不能插入。\n");
return 0;
}SS->top++;
// 栈指针先加1。memcpy(&SS->data[SS->top],ee,sizeof(ElemType));
// 用数组的下标访问。
// memcpy(SS->data+SS->top,ee,sizeof(ElemType));
// 采用指针运算也可以。return 1;
}// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS)
{
if (SS == NULL) return;
// 检查空指针。if (SS->top == -1) { printf("栈为空。\n");
return;
}int kk;
for (kk = 0;
kk <= SS->top;
kk++)
{
printf("SS[%d],value=https://www.it610.com/article/%d/n",kk,SS->data[kk]);
// 用数组的下标访问。
// printf("SS[%d],value=https://www.it610.com/article/%d/n",kk,*(SS->data+kk));
// 采用指针运算也可以。
}
}// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0;
// 检查空指针。if (SS->top == -1) { printf("栈为空。\n");
return 0;
}memcpy(ee,&SS->data[SS->top],sizeof(ElemType));
// 用数组的下标访问。
// memcpy(ee,SS->data+SS->top,sizeof(ElemType));
// 采用指针运算也可以。SS->top--;
// 栈指针减1。return 1;
}// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee)
{
if ( (SS == NULL) || (ee == NULL) ) return 0;
// 检查空指针。if (IsEmpty(SS) == 1) { printf("栈为空。\n");
return 0;
}memcpy(ee,&SS->data[SS->top],sizeof(ElemType));
// 用数组的下标访问。
// memcpy(ee,SS->data+SS->top,sizeof(ElemType));
// 采用指针运算也可以。return 1;
} 最终结果:
文章图片
三.栈的常用接口(C++中STL的使用):
构造函数:
stack stk;
//stack采用模板类实现, stack对象的默认构造形式
stack(const stack &stk);
//拷贝构造函数
赋值操作:
stack& operator=( const stack &stk) ;
//重载等号操作符数据存取:
push(elem);
//向栈顶添加元素
pop();
//从栈顶移除第一个元素
top();
//返回栈顶元素大小操作:
empty();
//判断堆栈是否为空
size();
//返回栈的大小操作案例:
#include
#include
using namespace std;
//栈stack容器
void test12()
{
//特点:符合先进后出数据结构
stacks;
//入栈
s.push(10);
s.push(20);
s.push(30);
s.push(40);
cout<<"栈的大小: "< 
文章图片
【数据结构与算法|数据结构与性质(2)栈(stack)基础板子】
推荐阅读
- 哈希|Leetcode二分查找11:1346. 检查整数及其两倍数是否存在
- leetcode|Leetcode二分查找4:69. x 的平方根
- c++|Leetcode二分查找9:744. 寻找比目标字母大的最小字母
- 蓝桥杯练习题|分解质因数
- 蓝桥杯练习题|【无标题】
- 《LeetCode算法全集》|?算法入门?《二分枚举》简单13 —— LeetCode 1351. 统计有序矩阵中的负数
- 经典程序|数据结构之用栈来解决括号匹配问题（Java实现）
- 线性表|大学数据结构之顺序表的实现（Java版本）
- 经典程序|数据结构之双向链表（Java实现）