广州学习网站建设,老公做网站网站推广,中文搜索引擎排名,北京网站建站系统平台由于是速成专题#xff0c;因此内容不会十分全面#xff0c;只会涵盖考试重点#xff0c;各学校课程要求不同 #xff0c;大家可以按照考纲复习#xff0c;不全面的内容#xff0c;可以看一下小编主页数据结构初阶的内容#xff0c;找到对应专题详细学习一下。 目录
一… 由于是速成专题因此内容不会十分全面只会涵盖考试重点各学校课程要求不同 大家可以按照考纲复习不全面的内容可以看一下小编主页数据结构初阶的内容找到对应专题详细学习一下。 目录
一、栈的基本概念
二、栈的存储结构
1. 顺序栈的实现
2. 顺序栈的基本实现
2.1 初始化
2.2 判断栈空
2.3 数据进栈
2.4 数据出栈
3. 共享栈
4. 栈的链式存储结构
三、栈的使用场景 一、栈的基本概念 栈是只允许在一端进行插入或删除操作的线性表。限定这种线性表只能在某一端进行插入和删除操作。栈操作的特性是后进先出。 栈顶线性表允许进行插入删除的那一端。 栈底不允许进行插入和删除的另一端。 空栈不含任何元素的空表。 n个不同元素进栈出栈元素不同排列的个数为。 第一部分大家记清楚栈只能从栈顶插入和删除以及后进先出的特性还要知道出栈种类计算。 二、栈的存储结构 栈是一种操作受限的线性表类似于线性表它也有对应的两种存储方式。
1. 顺序栈的实现 采用顺序存储的栈称为顺序栈它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素同时附设一个指针top指向当前栈顶元素的位置。
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //存放栈中元素int top; //栈顶指针
}SqStack; 2. 顺序栈的基本实现
2.1 初始化
void InitStack(SqStack S){S.top-1; //初始化栈顶指针
}
2.2 判断栈空
bool StackEmpty(SqStack S){if(S.top-1) //栈空return true;else //不空return false;
}
2.3 数据进栈
bool Push(SqStack S,ElemType x){if(S.topMaxSize-1) //栈满报错return false;S.data[S.top]x; //指针先加1再入栈注意顺序return true;
}
2.4 数据出栈
bool Pop(SqStack S,ElemType x){if(S.top-1) //栈空报错return false;xS.data[S.top--]; //先出栈指针再减1注意顺序return true;
}
例入栈序列为1,2,3,4,5则出栈序列不可能为
A. 4 3 5 1 2 B. 5 4 3 2 1 C. 4 5 3 2 1 D. 1 2 3 4 5 本道题选A。这类题是栈最常考的题目想要做好这种题一定要记住栈后进先出的特性。最简单的就是B1 2 3 4 5一口气全都进栈然后依次出栈故B正确。对于C1 2 3先入栈4入栈后立刻出栈然后5再入栈也立即出栈最后1 2 3再出栈就是4 5 3 2 1故C正确。对于D很明显就是进一个元素这个元素就立即出栈故D正确。而A1 2先进栈3 4入栈后立即出栈才会是4 3开头5入栈后立即出栈所以前3位是4 3 5但是1 2出栈只能是2 1故A错误。:
3. 共享栈 利用栈底位置相对不变的特性可让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸。 共享栈是为了更有效的利用存储空间两个栈的空间相互调节只有在整个存储空间被占满时才发生上溢有利于减少上溢发生。
4. 栈的链式存储结构 采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况。通常采用单链表实现并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点 Lhead指向栈顶元素。
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}*LiStack; 第二部分大家主要掌握顺序栈栈空/满的条件给出的例题非常重要。 三、栈的使用场景 栈能适用于递归算法表达式求值以及括号匹配等问题中。 第三部分就一句话三种场景大家记一下后面两个最常出现
