【王道】数据结构与算法栈(三)
✍、目录导图
目录
- ✍、目录导图
- 1、栈Stack
- 1.1、栈的重要术语
- 1.2、顺序栈的定义
- 1.3、链栈的定义
- 2、顺序栈的基本操作
- 2.1、让栈顶指针 top 指向栈顶元素的位置
- 2.1.1、初始化栈top=-1
- 2.1.2、判断栈是否为空栈
- 2.1.3、进栈(增)
- 2.1.4、出栈(删)
- 2.1.5、读取栈顶元素
- 2.2、让栈顶指针 top 指向栈顶元素 +1 的位置
- 2.2.1、初始化栈top=0
- 2.2.2、判断栈是否为空栈
- 2.2.3、进栈(增)
- 2.2.4、出栈(删)
- 2.2.5、读取栈顶元素
- 2.3、共享栈
- 2.4、小结
- 3、链栈的基本操作
- 4、小结
1、栈Stack
线性表是具有相同数据类型的 n(n≥0) 个数据元素的有限序列，其中 n 为表长，当 n = 0时线性表是一个空表。
栈：栈是只允许在一端进行插入(进栈)或删除操作(出栈)的线性表
1.1、栈的重要术语
栈的记忆：拿盘子，只能从一端拿
空栈：栈里面没有存任何数据元素（其实就是对应线性表的空表）
栈顶：允许插入和删除的一端
栈底：不允许插入和删除的一端
如图：
进栈顺序为：
- a1 -> a2 -> a3 -> a4 -> a5
出栈顺序为：
- a5 -> a4 -> a3 -> a2 -> a1
特点：
- 后进先出
- Last In First Out (LIFO)
1.2、顺序栈的定义
顺序栈：是只允许在一端进行插入或删除操作的顺序表
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针,指向的是栈顶元素,记录的是数组的下标
}SqStack; // Sq sequence 顺序的意思
例如一个栈如下：
1.3、链栈的定义
链栈：是只允许在一端进行插入或删除操作的单链表
- 头插法(对头结点的后插操作)建立单链表 对应 进栈
- 头删法(对头结点的后删操作)删除单链表 对应 出栈
所以链栈的定义和单链表差不多
typedef struct Linknode {ElemType data; // 数据域struct Linknode *next; // 指针域
}*LiStack; // 栈类型定义
2、顺序栈的基本操作
我们有两种设计栈的方式
- 让栈顶指针 top 指向栈顶元素的位置（栈满的条件为 ：
top = MaxSize -1） - 让栈顶指针 top 指向栈顶元素 +1 的位置（栈满的条件为 ：
top = MaxSize）
2.1、让栈顶指针 top 指向栈顶元素的位置
2.1.1、初始化栈top=-1
InitStack(&S)： 初始化栈，构造一个空栈S，分配内存空间
初始化栈就是让栈顶指针 top 指向 -1，因为栈顶指针指向的是栈顶元素，开始的时候没有元素，所以栈顶指针指向 0 这个位置是不合适的
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // Sq sequence 顺序的意思// 初始化栈
void InitStack(SqStack &S){S.top = -1; // 初始化栈顶指针
}void testStack(){SqStack S; // 声明一个顺序栈(分配空间)InitStack(S); // 初始化栈
}
2.1.2、判断栈是否为空栈
StackEmpty(S)判断一个栈 S 是否为空。若 S 为空，则返回 true，否则返回 false
判断栈是否为空只需要判断栈顶指针是否是 -1
// 判断空栈
bool StackEmpty(SqStack S){if(S.top == -1){return true; // 栈空}else{ return false; // 栈不空}
}
2.1.3、进栈(增)
Push(&S,x)进栈，若栈S未满，则将 x 加入使之成为新栈顶
进栈时先让栈顶指针 top 加一，之后将新元素放在 top 指针所指向的位置
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 新元素入栈
bool Push(SqStack &S,ElemType x){if(S.top == MaxSize - 1){return false; // 当top值 = 元素最大个数-1,栈满,报错}S.top = S.top + 1; // top指针先加1S.data[S.top] = x; // 新元素入栈// 上两行代码等价于 S.data[++S.top] = xreturn true;
}
2.1.4、出栈(删)
Pop(&S,&x)出栈，若栈S非空，则弹出栈顶元素，并用x返回
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 出栈操作
bool Pop(SqStack &S,ElemType &x){if(S.top == -1){return false; // 栈空,报错}x = S.data[S.top]; // 栈顶元素先出栈S.top = S.top -1; // 指针再减1// 上两行代码等价于 x = S.data[S.top--] return true;
}
2.1.5、读取栈顶元素
GetTop(S,&x)：读取栈顶元素，若栈 S 非空，则用 x 返回栈顶元素
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 读取栈顶元素
bool GetTop(SqStack S,ElemType &x){if(S.top == -1){return false; // 栈空,报错}x = S.data[S.top]; // x记录栈顶元素return true;
}
2.2、让栈顶指针 top 指向栈顶元素 +1 的位置
2.2.1、初始化栈top=0
初始化栈让栈顶指针 top 为 0
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 初始化栈
void InitStack(SqStack &S){S.top = 0; // 初始化指向0
}
2.2.2、判断栈是否为空栈
判断栈是否为空只需要判断栈顶指针是否是 0
// 判断空栈
bool StackEmpty(SqStack S){if(S.top == 0){return true; // 栈空}else{ return false; // 栈不空}
}
2.2.3、进栈(增)
这样的方式下先让新元素进栈，再让 top 指针指向下一个位置
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 新元素入栈
bool Push(SqStack &S,ElemType x){if(S.top == MaxSize - 1){return false; // 当top值 = 元素最大个数-1,栈满,报错}S.data[S.top] = x; // 先让新元素x进栈S.top = S.top + 1; // 之后再让 top 指针指向下一个位置// 上两行代码等价于 S.data[S.top++] = xreturn true;
}
2.2.4、出栈(删)
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 出栈操作
bool Pop(SqStack &S,ElemType &x){if(S.top == -1){return false; // 栈空,报错}S.top = S.top - 1; // 先让栈顶指针向下移一位x = S.data[S.top]; // 再让栈顶指针指向的元素出栈// 上两行代码等价于 x = S.data[--S.top] return true;
}
2.2.5、读取栈顶元素
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct { ElemType data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针
}SqStack; // 读取栈顶元素
bool GetTop(SqStack S,ElemType &x){if(S.top == 0){return false; // 栈空,报错}x = S.data[S.top -1]; // x记录栈顶元素return true;
}
2.3、共享栈
共享栈：两个栈共享同一片空间
让两个栈共享同一片空间， 0 号栈栈顶指针指向
#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; // 静态数组存放栈中元素int top0; // 0 号栈栈顶指针int top1; // 1 号栈栈顶指针
}
// 初始化栈
void InitStack(ShStack &S){S.top0 = -1; // 初始化栈顶指针S.top1 = MaxSize;
}
2.4、小结
3、链栈的基本操作
- 链栈：用链式存储方式实现的栈叫做链栈
- 链栈的操作与链表类似，入栈和出栈的操作都会在链表的表头进行。
- 链栈是运算受限的单链表，只能在链表头部进行操作。
4、小结
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！