数据结构与算法

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语言实现栈和队列

1.1 栈基本概念

🏃 回顾一下我们之前学习过的线性表，我们可以在表中任意位置插入和删除元素
🏃 如果插入和删除操作只允许在一端进行的话，那么我们赋予线性表一个特殊的名字 - 栈（Stack）
🏃 栈：只允许在一端进行插入和删除操作的线性表

🏃 其中进行插入和删除操作的一端称为 - 栈顶（Top）
🏃 另一端称为 - 栈底（Bottom）
🏃 栈的插入操作称为 - 进栈（Push）
🏃 栈的删除操作称为 - 出栈（Pop）

💘 结构图如下：

🏃 由上图可以看出，后进去的元素，出去的时候最先出去
🏃 以此，栈有一个特性，也是原则 - 后进先出 LIFO（Last In First Out）

1.2 栈的实现

🏃 结合我们在线性表学到的知识：线性表的实现可以用顺序表（数组）或者链表
🏃 以此我们来讨论一下，栈的实现选择顺序表还是链表

🏃 由栈的结构可知，我们对栈的操作大多都是在栈顶实现的。
🏃 如果用链表，我们需要频繁找到链表的尾部节点，比较费劲
🏃 而顺序表可以通过表中有效元素个数，轻易的访问到最后一个元素

💘 以此，我们可以选择数组来实现栈

1.2.1 栈的创建（Stack st）

💘 我们可以用定长的静态数组创建栈，也可以用动态增长的数组创建栈

💘 静态栈的创建

typedef int STDataType;//静态栈#define MAX_SIZE 10typedef 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）

🏃 动态申请一个数组，修改栈里面的参数

//初始化 - 默认容量是10void StackInit(Stack* st)//由于修改里面的参数，以此需要传地址{//默认容量是10st->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;elsest->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;}

💘 以上就是栈的重点内容，其实在我们学完线性表后，只要注意好细节，栈的自主实现已经不成问题

//后记

🏃 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。