【数据结构从青铜到王者】第四篇:数据结构之栈

谁践踏了优雅 2023-01-16 06:28 115阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

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

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、栈的概念及结构
 *   *   *  1.栈的概念
         *  2.栈的结构
 *  二、栈的实现
 *   *   *  1.定义数组动态增长的栈struct Stack
         *  2.初始化栈StackInit函数
         *  3.销毁栈StackDestroy函数
         *  4.入栈StackPush函数
         *  5.出栈StackPop函数
         *  6.获取栈顶数据StackTop函数
         *  7.判断栈是否为空StackEmpty函数
         *  8.求出栈的大小StackSize函数
 *  总结

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

# 前言 #

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

# 一、栈的概念及结构 #

### 1.栈的概念 ###

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

### 2.栈的结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

# 二、栈的实现 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]

### 1.定义数组动态增长的栈struct Stack ###

代码如下：

typedef int STDataType;
    struct Stack       //动态增长的栈
    { 
    	STDataType* a;
    	int top;        //栈顶
    	int capacity;   //容量
    };

### 2.初始化栈StackInit函数 ###

先给栈分配4个容量的空间，方便以后扩容。  
代码如下：

void StackInit(struct Stack* pst)
    { 
    	assert(pst);
    	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
    	pst->top = 0;
    	pst->capacity = 4;
    }

### 3.销毁栈StackDestroy函数 ###

释放出动态增加的空间，防止内存泄露  
代码如下：

void StackDestroy(struct Stack* pst)
    { 
    	assert(pst);
    	free(pst->a);
    	pst->a = NULL;
    	pst->a = pst->capacity = 0;
    }

### 4.入栈StackPush函数 ###

首先判断栈的容量，然后在栈顶写入数据。  
代码如下：

void StackPush(struct Stack* pst, STDataType x)
    { 
    	assert(pst);
    	if (pst->top == pst->capacity)   //容量不够则增加容量
    	{ 
    		STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType)*pst->capacity * 2);
    		if (tmp == NULL)
    		{ 
    			printf("开辟空间失败!\n");
    			exit(-1);  //0是正常退出，-1是异常退出
    		}
    		pst->a = tmp;
    		pst->capacity = pst->capacity * 2;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }

### 5.出栈StackPop函数 ###

在栈顶删除数据，注意判断栈是否为空。  
代码如下：

void StackPop(struct Stack* pst)
    { 
    	assert(pst);
    	assert(!(StackEmpty(pst)));
    	pst->top--;
    }

### 6.获取栈顶数据StackTop函数 ###

代码如下：

STDataType StackTop(struct Stack* pst)
    { 
    	assert(pst);
    	assert(!(StackEmpty(pst)));
    	return pst->a[pst->top - 1];  //top减一就是栈顶数据
    }

### 7.判断栈是否为空StackEmpty函数 ###

直接看栈顶top是否有数据  
代码如下：

bool StackEmpty(struct Stack* pst)
    { 
    	assert(pst);
    	return pst->top == 0;
    }

### 8.求出栈的大小StackSize函数 ###

其中top从0开始top的大小就是栈中数据的多少  
![在这里插入图片描述][20210424143159894.png]  
代码如下：

STDataType StackSize(struct Stack* pst)
    { 
    	return pst->top;
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]

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

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了数据结构中栈的的使用，对于栈提供了一些简便方法帮助我们解题，能使我们快速便捷地处理数据的函数和方法。另外这个结构虽然结构复杂，但是使用代码实现起来更容易写，以后会发现结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。

![在这里插入图片描述][20210424143437674.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/c4883714d62a48bf9b514c5dd31a0c0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/bb56b787e2364cae9cf7b5b63d8b075d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/541a7f71d5924c899de8099868de499d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/3fe19e6664074297b64d35f2e8826e68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/1dde67c38b974fe1a6fba4dd8c20b333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221022/b86956c807a24c6b87e49eb7192a29bd.png
[20210424143159894.png]: /images/20221022/eac173a6a1ec49f58b5c6511deeebdea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221022/e3e3a2acdbb94f20b990f8b443f0cdf7.png
[20210424143437674.png_pic_center]: /images/20221022/7db65816ba9e4789bd2c223db8691b4d.png