欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
1.栈的基本概念
1.1栈的定义：
- 栈（Stack）是只允许在一端进行插入或删除操作的线性表
- 逻辑结构：与普通线性表相同
- 数据的运算：插入、删除操作有区别
- 栈顶：允许插入和删除的一端，对应元素被称为栈顶元素
- 栈底：不允许插入和删除的一端，对应元素被称为栈底元素
- 特点：后进先出Last In First Out（LIFO）
1.2栈的基本操作：
- InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。
- DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。
- Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
- Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
- GetTop(S, &x)：读栈顶元素。若栈S非空，则用x返回栈顶元素
- StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。
1.3出栈顺序数量：
- n个不同元素进栈，出栈元素不同排列的个数为
-
编辑 - 上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明
2.栈的顺序存储结构
- 2.1顺序栈的定义和初始化：
编辑
- 2.2顺序栈的定义代码实现：
//定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶元素 }SqStack; void testStack(){ SqStack S; //声明一个顺序栈(分配空间) //连续的存储空间大小为 MaxSize*sizeof(ElemType) }
- 2.3顺序栈的基本操作代码实现：
//定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶元素 }SqStack; //初始化栈 void InitStack(SqStack &S){ S.top = -1; //初始化栈顶指针 } //判栈空 bool StackEmpty(SqStack S){ if(S.top == -1) //栈空 return true; else //栈不空 return false; } //出栈 bool Pop(SqStack &x, ElemType &x){ if(S.top == -1) //栈空 return false; x = S.data[S.top]; //先出栈 S.top = S.top - 1; //栈顶指针减1 return true; /* x = S.data[S.top--]; */ //只是逻辑上的删除，数据依然残留在内存里 } //读栈顶元素 bool GetTop(SqStack S, ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; //x记录栈顶元素 return true; } void testStack(){ SqStack S; //声明一个顺序栈(分配空间) InitStack(S); //... }
- 2.3.1进栈操作：
编辑
- 2.3.2进栈操作代码实现：
bool Push(SqStack &S, ElemType x){ if(S.top == MaxSize - 1) //栈满 return false; S.top = S.top + 1; //指针先加1 S.data[S.top] = x; //新元素入栈 /* S.data[++S.top] = x; */ return true; }
- 2.3.3出栈操作：
编辑
- 2.3.4进栈操作代码实现：
bool Pop(SqStack &x, ElemType &x){ if(S.top == -1) //栈空 return false; x = S.data[S.top]; //先出栈 S.top = S.top - 1; //栈顶指针减1 return true; /* x = S.data[S.top--]; */ //只是逻辑上的删除，数据依然残留在内存里 }
- 2.3.5读取栈顶元素：
编辑
- 2.3.6读取栈顶元素代码实现：
bool GetTop(SqStack S, ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; //x记录栈顶元素 return true; } void testStack(){ SqStack S; //声明一个顺序栈(分配空间) InitStack(S); //... }
- 注意：也可以让栈顶指针top先指向0，每次进栈S.top++，出栈--S.top
3.共享栈：
- 使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生
- 两个栈共享同一片空间，0、1号栈朝着同一方向进栈
- 栈满的条件：top0 + 1 == top1
编辑
3.1共享栈的定义和初始化代码实现：
//定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top0; //0号栈栈顶指针 int top1; //1号栈栈顶指针 }ShStack; //初始化栈 void InitSqStack(ShStack &S){ S.top0 = -1; //初始化栈顶指针 S.top1 = MaxSize; }
栈满条件：
top1-top0=1
4.栈的链式存储结构
4.1栈的链式存储实质：
- 进栈：头插法建立单链表，也就是对头结点的后插操作
- 出栈：单链表的删除操作，对头结点的“后删”操作
- 推荐使用不带头结点的链栈
- 创销增删查的操作参考链表
4.2链栈的定义：
-
编辑
4.3链栈的定义代码实现：
struct Linknode{ int data; //数据域 Linknode *next; //指针域 }Linknode,*LiStack; typedef Linknode *Node; //结点结构体指针变量 typedef Node List; //结点结构体头指针变量
4.4带头结点的链栈基代码实现如下：
1. 初始化
void InitStack(LiStack &L){ //L为头指针 L = new Linknode; L->next = NULL; }
2.判栈空
bool isEmpty(LiStack &L){ if(L->next == NULL){ return true; } else return false; }
3. 进栈
void pushStack(LiStack &L, int x){ Linknode s; //创建存储新元素的结点 s = new Linknode; s->data = x; //头插法 s->next = L->next; L->next = s; }
4.出栈
bool popStack(LiStack &L, int &x){ Linknode s; if(L->next == NULL) //栈空不能出栈 return false; s = L->next; x = s->data; L->next = L->next->next; delete(s); return true; }
4.5不带头结点的链栈代码实现基本操作如下：
1.初始化
void initStack(LiStack &L){ L=NULL; }
2.判栈空
bool isEmpty(LiStack &L){ if(L == NULL) return true; else teturn false; }
3.进栈
void pushStack(LiStack &L, int x){ Linknode s; //创建存储新元素的结点 s = new Linknode; s->next = L; L = s; }
4.出栈
bool popStack(LiStack &L, int &x){ Linknode s; if(L = NULL) //栈空不出栈 return false; s = L; x = s->data; L = L->next; delete(s); return true; }
