栈的概念及结构（C语言实现栈）

Love The Way You Lie 2023-09-27 23:26 88阅读 0赞

**目录：**

一、栈的概念

二、栈的实现

三、代码实现以及详细解释

1. 初步介绍

2. 定义结构体，以及栈内数据类型

3. 初始化栈 void STInit(ST\* pst);

4. 销毁栈 void STDestroy(ST\* pst);

5.添加数据 void STPush(ST\* pst, STDataType x);

6.删除数据 void STPop(ST\* pst)；

7. 弹出数据 STDataType STTop(ST\* pst);

8. 判断是否为空 bool STEmpty(ST\* pst);

9. 判断大小 int STSize(ST\* pst);

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

## 前言以及成型代码： ##

**学习完数据表和链表以后我们来学习一个新的数据结构：栈 。 还是老套路先把成型代码给各位看关老爷呈上方便有一个初步了解。更重要的是可以方便CV工程师的工作**

#define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.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);
    
    // 判断大小
    int STSize(ST* pst);
    void STInit(ST* pst)
    {
    	assert(pst);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 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)
    {
    	if (pst->capacity == pst->top)
    	{
    		int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2);
    		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			return;
    		}
    		pst->a = tmp;
    		pst->capacity = newcapacity;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }
    
    // 删除数据
    void STPop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));
    	pst->top--;
    }
    
    // 弹出数据
    STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));
    	return pst->a[pst->top - 1];
    }
    
    // 判断是否为空
    bool STEmpty(ST* pst)
    {
    	assert(pst);
    	return pst->top == 0;
    }
    
    // 判断大小
    int STSize(ST* pst)
    {
    	assert(pst);
    	return pst->top;
    }

## 一、栈的概念 ##

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

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

![9805811d1ee04e64a665114dc7540ce9.png][]

## 二、栈的实现 ##

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

![7dd1434d5a664059822f3e9ece27550b.png][]

![16677d2feacd4eab81a9b839c12e9bf1.png][]

## 三、代码实现以及详细解释 ##

### 1. 初步介绍 ###

> 1.  定义结构体，以及栈内数据类型
> 2.  初始化栈 void STInit(ST\* pst);
> 3.  销毁栈 void STDestroy(ST\* pst);
> 4.  添加数据 void STPush(ST\* pst, STDataType x);
> 5.  删除数据 void STPop(ST\* pst)；
> 6.  弹出数据 STDataType STTop(ST\* pst);
> 7.  判断是否为空 bool STEmpty(ST\* pst);
> 8.  判断大小 int STSize(ST\* pst);

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

### 2. 定义结构体，以及栈内数据类型 ###

**代码：**

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    
    typedef int STDataType;  //定义栈内数据类型，方便后面修改
    typedef struct Stack    //创建栈的基本结构
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }ST;

这几行代码是栈的地基，也是这个结构中最简单的代码了。

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

### 3. 初始化栈 void STInit(ST\* pst); ###

**代码：**

// 初始化栈
    void STInit(ST* pst)
    {
    	assert(pst);   //判断是否为空指针
    	pst->a = NULL; //栈为空的，所以先初始化为空指针
    	pst->top = 0;  
    	pst->capacity = 0;
    }

初始化栈，顾名思义就是把栈的结构上面添加一些初始值。让前面的地基有框架。

### 4. 销毁栈 void STDestroy(ST\* pst); ###

**代码：**

// 销毁栈
    void STDestroy(ST* pst)
    {
    	assert(pst);
    	free(pst->a);  //释放指针
    	pst->a = NULL; //置空指针a
    	pst->top = 0;  //把栈顶的位置降低，释放数据
    	pst->capacity = 0;//把栈的大小置为0
    }

创建以后肯定是要销毁的，要不然就会造成内存泄漏。

### 5.添加数据 void STPush(ST\* pst, STDataType x); ###

**代码：**

// 添加数据
    void STPush(ST* pst, STDataType x)
    {
    	if (pst->capacity == pst->top)  //判断是否要扩容
    	{
    		int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2); //扩容步骤，当为空栈时扩基础的大小，不为空则扩成原来的二倍
    		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));//使用realloc扩出来一定的空间
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			return;
    		}
    		pst->a = tmp;   //初始化这一块空间
    		pst->capacity = newcapacity;
    	}
    	pst->a[pst->top] = x;  //把x的直插入到栈的顶部
    	pst->top++;
    }

添加数据也是很重要的一个步骤，这一步直接决定了这个栈的成功与否。添加的时候要首先判断后面的空间是否足够，够的话直接加上去，不够的话就扩容。

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

### 6.删除数据 void STPop(ST\* pst)； ###

// 删除数据
    void STPop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));  //判断是否为空
    	pst->top--;
    }

删除数据的时候要借助后面的判空函数，为空就不能再删除了

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

### 7. 弹出数据 STDataType STTop(ST\* pst); ###

**代码：**

// 弹出数据
    STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(!(STEmpty(pst)));
    	return pst->a[pst->top - 1];
    }

弹出数据就是：调用完这个函数以后可以返回栈顶的值

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

### 8. 判断是否为空 bool STEmpty(ST\* pst); ###

// 判断是否为空
    bool STEmpty(ST* pst)
    {
    	assert(pst);
    	return pst->top == 0;//判空
    }

判空就是看里面还有数据没有了，有的话返回false 没有数据也就是空值的状态就返回true

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

### 9. 判断大小 int STSize(ST\* pst); ###

**代码：**

// 判断大小
    int STSize(ST* pst)
    {
    	assert(pst);
    	return pst->top;
    }

直接返回栈顶就可以了

[9805811d1ee04e64a665114dc7540ce9.png]: https://img-blog.csdnimg.cn/9805811d1ee04e64a665114dc7540ce9.png
[7dd1434d5a664059822f3e9ece27550b.png]: https://img-blog.csdnimg.cn/7dd1434d5a664059822f3e9ece27550b.png
[16677d2feacd4eab81a9b839c12e9bf1.png]: https://img-blog.csdnimg.cn/16677d2feacd4eab81a9b839c12e9bf1.png