【数据结构】C语言实现栈

绝地灬酷狼 2024-04-22 02:31 43阅读 0赞

**目录**

前言

1. 栈

1.1 栈的概念

1.2 栈的结构

2. 栈的实现

2.1 栈的初始化

2.2 入栈

2.3 出栈

2.4 读取栈顶元素

2.5 判断栈空

2.6栈的销毁

3. 栈完整源代码

Stack.h

Stack.c

--------------------

>  *  ?个人主页：[库库的里昂][Link 1]
>  *  ?C/C++领域新星创作者
>  *  ?欢迎 ?点赞✍评论⭐收藏
>  *  ✨收录专栏：[数据结构与算法][Link 2]
>  *  ?希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！?

### 前言 ###

> 在前几期的学习中，我们认识了顺序表和链表这两种线性表，而在本期学习中，我们将会认识别的线性表。跟随我们的脚本，看看栈和队列有怎样的特点。

### 1. 栈 ###

#### 1.1 栈的概念 ####

> 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

*  压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
 *  出栈：栈的删除操作叫做出栈。出数据也在栈顶。

#### 1.2 栈的结构 ####

![562e1373c58e4d87956635a2e181b360.png][]

![371255695e294cd39fcf67396bfc0f88.png][]

### 2. 栈的实现 ###

> 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

![a7b0e58ea268411e8b4b4b97d6bb511f.png][]

![e847ee4227084b6397b8c9f946c65e5f.png][]

#### 2.1 栈的初始化 ####

> 我们将结构体的所有元素都初始化为0。这里与我们在顺序表中的初始化不同，在顺序表中我们在初始化时就开辟了空间，下面我们会介绍另一种方式。

void STInit(ST* pst)
    {
    	assert(pst);
    
    	pst->a = NULL;
    	pst->capacity = 0;
    	pst->top = 0;
    }

#### 2.2 入栈 ####

> 在进栈时可能遇到容量为零，所以我们使用一个条件判断，来确定容量。因为top为0，所以它表示的是下一个元素的下标，**要先赋值，再top++**。

void STPush(ST* pst, STDataType x)
    {
    	assert(pst);
    
    	if (pst->top == pst->capacity)
    	{
    		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    		STDataType* tmp = calloc(pst->a, sizeof(STDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("calloc fail");
    			return;
    		}
    		pst->a = tmp;
    		pst->capacity = newcapacity;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }

> **malloc 和 realloc 开辟空间的区别就是 realloc 要传递一个指针，而当我们给 realloc 传递一个空指针，那么它的功能就和 malloc 相同。**

#### 2.3 出栈 ####

> 出栈只需要将 top --就访问不到这个元素了。在出栈时我们要判断栈中是否还有元素。

void STPop(ST* pst)
    {
    	assert(pst);
    	assert(pst->top > 0);
    
    	pst->top--;
    }

#### 2.4 读取栈顶元素 ####

> 栈顶元素就是我们插入的最后一个元素。由于top表示的是下一个元素的下标，所以读取栈顶元素是top要减1。

STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(pst->top > 0);
    
    	return pst->a[pst->top - 1];
    }

#### 2.5 判断栈空 ####

bool STEmpty(ST* pst)
    {
    	assert(pst);
    
    	return pst->top == 0;
    }

#### 2.6栈的销毁 ####

> 这里使用的内存是动态开辟的，因此在我们使用完后要及时释放掉内存，否则会造成内存泄漏。

void STDestroy(ST* pst)
    {
    	assert(pst);
    
    	free(pst->a);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }

### 3. 栈完整源代码 ###

#### Stack.h ####

#include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    typedef int STDataType;
    
    typedef struct Stack
    {
    	STDataType* a;
    	int top;		// 标识栈顶位置的
    	int capacity;
    }ST;
    
    void STInit(ST* pst);//初始化
    
    void STDestroy(ST* pst);//销毁
    
    void STPush(ST* pst, STDataType x);//入栈
    
    void STPop(ST* pst);//出栈
    
    STDataType STTop(ST* pst);//读取栈顶元素
    
    bool STEmpty(ST* pst);//判断栈空

#### Stack.c ####

#include"Stack.h"
    
    void STInit(ST* pst)
    {
    	assert(pst);
    
    	pst->a = NULL;
    	pst->capacity = 0;
    	pst->top = 0;
    }
    
    void STDestroy(ST* pst)
    {
    	assert(pst);
    
    	free(pst->a);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }
    
    void STPush(ST* pst, STDataType x)
    {
    	assert(pst);
    
    	if (pst->top == pst->capacity)
    	{
    		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    		STDataType* tmp = calloc(pst->a, sizeof(STDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("calloc fail");
    			return;
    		}
    		pst->a = tmp;
    		pst->capacity = newcapacity;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }
    
    void STPop(ST* pst)
    {
    	assert(pst);
    	assert(pst->top > 0);
    
    	pst->top--;
    }
    
    STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(pst->top > 0);
    
    	return pst->a[pst->top - 1];
    }
    
    bool STEmpty(ST* pst)
    {
    	assert(pst);
    
    	return pst->top == 0;
    }

> **本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。**

![a19b099e0e6044cd9224cf6e5b657deb.png][]

[Link 1]: https://blog.csdn.net/m0_68662723
[Link 2]: http://t.csdnimg.cn/wUE8D
[562e1373c58e4d87956635a2e181b360.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/7b11554940824830af76dfe1a63a64e3.png
[371255695e294cd39fcf67396bfc0f88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/4aeac95637a143e8a095aa4e83b51807.png
[a7b0e58ea268411e8b4b4b97d6bb511f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/414f8d6110a5489eb7bb79b735d8ee43.png
[e847ee4227084b6397b8c9f946c65e5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/71e757ddefed498fb3afebebc3c5ee70.png
[a19b099e0e6044cd9224cf6e5b657deb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/cb0ea53e804c459eadae898a3aff0301.png