Lesson04 - *** 作受限的线性表 - 栈
文章目录
- 数据结构与算法
- 前言
- 1.1 栈基本概念
- 1.2 栈的实现
- 1.2.1 栈的创建(Stack st)
- 1.2.2 初始化(Init)
- 1.2.3 进栈(入栈 - Push)
- 1.2.4 出栈(Pop)
- 1.2.5 获得栈顶元素(StackTop)
- 1.2.6 检查栈是非为空(IsStackEmpty)
- 1.2.7 销毁栈(StackDestroy)
- //后记
前言
💘 Lesson04 主要讲解数据结构中两个 *** 作受限的线性表 - 栈和队列
💘 重点讲解栈和队列的基本概念和特点
💘 然后用C语言模拟实现栈和队列
💘 本篇文章没有伪代码,帮助大家在理解的前提下,自己动手用C语言实现栈和队列
🏃 回顾一下我们之前学习过的线性表,我们可以在表中任意位置插入和删除元素
🏃 如果插入和删除 *** 作只允许在一端进行的话,那么我们赋予线性表一个特殊的名字 - 栈(Stack)
🏃 栈:只允许在一端进行插入和删除 *** 作的线性表
🏃 其中进行插入和删除 *** 作的一端称为 - 栈顶(Top)
🏃 另一端称为 - 栈底(Bottom)
🏃 栈的插入 *** 作称为 - 进栈(Push)
🏃 栈的删除 *** 作称为 - 出栈(Pop)
💘 结构图如下:
1.2 栈的实现🏃 由上图可以看出,后进去的元素,出去的时候最先出去
🏃 以此,栈有一个特性,也是原则 - 后进先出 LIFO(Last In First Out)
🏃 结合我们在线性表学到的知识:线性表的实现可以用顺序表(数组)或者链表
🏃 以此我们来讨论一下,栈的实现选择顺序表还是链表
🏃 由栈的结构可知,我们对栈的 *** 作大多都是在栈顶实现的。
🏃 如果用链表,我们需要频繁找到链表的尾部节点,比较费劲
🏃 而顺序表可以通过表中有效元素个数,轻易的访问到最后一个元素
💘 以此,我们可以选择数组来实现栈
1.2.1 栈的创建(Stack st)💘 我们可以用定长的静态数组创建栈,也可以用动态增长的数组创建栈
💘 静态栈的创建
typedef int STDataType;
//静态栈
#define MAX_SIZE 10
typedef struct Stack
{
STDataType a[MAX_SIZE];//定长的数组来存栈的元素
int top;//用来记录栈顶的位置,可以记录元素的个数
}Stack;
int main()
{
Stack st;
return 0;
}
💘 动态栈的创建
typedef int STDataType;
//动态栈
typedef struct Stack
{
STDataType* a;//可以用malloc申请可以动态增长的数组
int top;//记录栈顶元素的位置
int capacity;//记录最大容量,方便扩容
}Stack;
int main()
{
Stack st;
return 0;
}
1.2.2 初始化(Init)
🏃 动态申请一个数组,修改栈里面的参数
//初始化 - 默认容量是10
void StackInit(Stack* st)//由于修改里面的参数,以此需要传地址
{
//默认容量是10
st->capacity = 10;
int* tmp = (int*)malloc(sizeof(int) * st->capacity);
if (tmp == NULL)
{
perror("StackInit::malloc");
}
st->a = tmp;
st->top = 0;//没有元素时,top指向0位置
}
1.2.3 进栈(入栈 - Push)
🏃 进栈元素插入 top 所指的位置,然后将 top的值 +1
🏃 但是如果,top == capacity,说明不能再插入元素了,需要增容
🏃 因此我们第一步先判断是否已满
//进栈
void StackPush(Stack* st, STDataType x)
{
//进栈第一步先判断是否已满
if (st->top == st->capacity)
{
STDataType* tmp = (int*)realloc(st->a, sizeof(int) * st->capacity * 2);
if (tmp == NULL)
{
perror("StackPush::realloc");
}
st->a = tmp;
st->capacity *= 2;//增容后一定要更改最新容量
}
//进栈 *** 作仅需一步
st->a[st->top++] = x;
}
1.2.4 出栈(Pop)
🏃 只需将 top 的值 -1 即可在逻辑上删除元素
🏃 但是需要注意一点,如果栈为空,则不能出栈
//出栈
void StackPop(Stack* st)
{
if (st->top == 0)
return;
else
st->top--;
}
1.2.5 获得栈顶元素(StackTop)
🏃 栈顶元素就是 top 所指位置的前一个
ps: 由于很简单,这里就不给图咯
//获取栈顶元素
STDataType StackTop(const Stack* st)
{
return st->a[st->top - 1];
}
1.2.6 检查栈是非为空(IsStackEmpty)
🏃 如果栈的 top 值为0,则栈为空
//判空
bool IsStackEmpty(Stack* st)
{
return st->top == 0;//如果为空,判断为真,返回true,否则返回false
}
1.2.7 销毁栈(StackDestroy)
🏃 清空栈内数据
//销毁栈
void StackDestroy(Stack* st)
{
free(st->a);
st->a = NULL;
st->capacity = 0;
st->top = 0;
}
💘 以上就是栈的重点内容,其实在我们学完线性表后,只要注意好细节,栈的自主实现已经不成问题
//后记🏃 以后每周会更新一到两篇学习数据结构的笔记,用来记录自己的学习历程,复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方,希望大佬们在评论区指出,本人会虚心接受并且改正。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)