关键词:
✍、目录导图
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指针先加1
S.data[S.top] = x; // 新元素入栈
// 上两行代码等价于 S.data[++S.top] = x
return 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++] = x
return 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、小结
王道数据结构与算法队列queue(代码片段)
✍、目录脑图1、队列Queue线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。栈:栈是只允许在一端进行插入(进栈)或删除操作(出栈)的线性表队列:队列是只... 查看详情
数据结构与算法王道考研数据结构与算法2021配套大题第三章(java语言描述)(代码片段)
3.1栈3、出入栈是否非法 挺好写的,我感觉。publicstaticbooleanfunc(char[]arr) intlength=0; for(inti=0;i<arr.length;i++) if(arr[i]=='O')length--; if(arr[i]=='I')length++; if(length<0)returnfalse; returnlength&... 查看详情
王道数据结构与算法之排序算法(代码片段)
这里是【王道计算机考研】数据结构与算法最终篇*★由于数据结构开篇较早,初始是按照【2021】年大纲来记录的笔记,并且中途结合了青岛大学王卓老师的课程来辅助理解,所以大家在浏览时会发现文章标题我已经... 查看详情
王道数据结构与算法串(代码片段)
✍、目录脑图目录♥✍、目录脑图1、串1.1、串和线性表1.2、串的基本操作1.3、串的存储结构1.3.1、串的顺序存储1.3.2、串的链式存储1.4、串的基本操作的实现1.4.1、求子串1.4.2、比较操作1.4.3、定位操作1.5、串的朴素模式匹配算法1... 查看详情
数据结构与算法王道考研数据结构与算法2021配套大题(java语言描述)(代码片段)
2.2.3顺序表 顺序表内容如下:classArrayList publicint[]arr; publicintlength; publicArrayList(int[]arr,intlength) if(arr.length<length) /*给数组扩容,不过我这里没有实现扩容的方法,所以直接抛出异常*/ thrownew 查看详情
王道数据结构与算法树(八——1)(代码片段)
✍、目录脑图树[第一部分]✍、目录脑图1、树1.1、树的基本概念1.2、结点之间的关系描述1.3、有序树、无序树、森林1.4、树的常考性质2、二叉树2.1、满二叉树2.2、完全二叉树2.3、二叉排序树2.4、平衡二叉树2.5、总结3、二叉树的... 查看详情
王道数据结构与算法树(八——2)(代码片段)
✍、目录脑图目录✍、目录脑图1、线索二叉树1.1、线索二叉树的存储结构1.1.1、中序线索二叉树的存储1.2、先序线索二叉树1.3、后序线索二叉树1.4、三种线索二叉树的对比2、二叉树的线索化2.1、中序线索化2.2、先序线索化2.3、... 查看详情
王道数据结构与算法之排序算法(代码片段)
这里是【王道计算机考研】数据结构与算法最终篇*★由于数据结构开篇较早,初始是按照【2021】年大纲来记录的笔记,并且中途结合了青岛大学王卓老师的课程来辅助理解,所以大家在浏览时会发现文章标题我已经... 查看详情
《数据结构与算法》-3-栈和队列(代码片段)
...构4.3矩阵的压缩存储?该系列博客的目的是为了学习一遍数据结构中常用的概念以及常用的算法,为笔试准备;主要学习过程参考王道的《2018年-数据结构-考研复习指导》;已总结章节:《数据结构与算法》-1-绪论《数据结构与... 查看详情
数据结构与算法—数组栈和链表栈(代码片段)
数据结构与算法—数组栈和链表栈🌈一览众山小数据结构与算法—数组栈和链表栈栈介绍栈图解栈实现数组实现栈实现思路实现代码单链表实现栈实现思路(图解)实现代码栈总结栈力扣栈介绍栈,存储货物或供旅客住宿的地方... 查看详情
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情
数据结构与算法:栈+队列+递归(代码片段)
【栈】Python实现:1.用数组实现一个顺序栈classSStack():def__init__(self):self._elems=[]defis_empty(self):returnself._elems==[]deftop(self):ifself._elems==[]:raiseStackUnderflow("inSStack.top()")returnself._elems[-1]de 查看详情
结构与算法-----栈2(代码片段)
1、栈-概念 栈是一种用于存储数据的简单数据结构,类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表... 查看详情
结构与算法-----栈(代码片段)
...了数组,数组更多的是用来进行数据的存储,我们期望的数据结构是插入、删除和查找性能都比较好。对于无序数组,插入快,但是删除和查找都很慢,为了解决这些问题,后面我们会讲解比如二叉树、哈希表的数据结构。 ... 查看详情
数据结构与算法同种算法分别用递归/回溯与栈实现(代码片段)
一、阶乘importjava.util.Stack;publicclassMain publicstaticintfact1(intn) if(n==0)return1; elsereturnn*fact1(n-1); publicstaticintfact2(intn) intans=1; Stack<Integer>stack=ne 查看详情
数据结构与算法--栈和队列(代码片段)
栈定义栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说,表尾端有其特殊含义,称为栈顶,表头端称为栈底。不含元素的空表称为空栈。栈顶实现元素的进出,栈的修改遵循后进先出的原则。因此,栈又称为后进... 查看详情
数据结构与算法学习笔记栈和队列ⅰ(代码片段)
数据结构与算法学习笔记(5)栈和队列文章目录数据结构与算法学习笔记(5)栈和队列一.栈和队列的定义和特点1.栈的定义和特点相关概念示意图栈与一般线性表的不同2.队列的定义和特点相关概念二.案例引入1.栈的典型案例进制转... 查看详情
考研数据结构与算法栈和队列(代码片段)
文章目录一、栈1.1顺序栈1.1.1顺序栈代码实现1.1.1.1初始化1.1.1.2判栈空1.1.1.3进栈1.1.1.4出栈1.1.1.5读栈顶元素1.2链栈1.2.1链栈的代码实现1.2.1.1初始化1.2.1.2判栈空1.2.1.3进栈1.2.1.4出栈1.2.1.5读取栈顶元素1.3共享栈1.4实际应用1.4.1进制转... 查看详情