由于是速成专题,因此内容不会十分全面,只会涵盖考试重点,各学校课程要求不同 ,大家可以按照考纲复习,不全面的内容,可以看一下小编主页数据结构初阶的内容,找到对应专题详细学习一下。
目录
一、栈的基本概念
二、栈的存储结构
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.top==MaxSize-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;
x=S.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。这类题是栈最常考的题目,想要做好这种题一定要记住栈后进先出的特性。最简单的就是B,1 2 3 4 5一口气全都进栈,然后依次出栈,故B正确。对于C,1 2 3先入栈,4入栈后立刻出栈,然后5再入栈也立即出栈,最后1 2 3再出栈,就是4 5 3 2 1,故C正确。对于D很明显就是进一个元素,这个元素就立即出栈,故D正确。而A,1 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;
第二部分大家主要掌握顺序栈栈空/满的条件,给出的例题非常重要。
三、栈的使用场景
栈能适用于递归算法,表达式求值以及括号匹配等问题中。
第三部分就一句话,三种场景大家记一下,后面两个最常出现!