数据结构04 - 手把手带你拿捏 *** 作受限的线性表 - 栈（附带超详细的用C语言模拟实现栈）

class="superseo">数据结构与算法

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 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;
}

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

//后记

🏃 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。

🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。