数据结构篇四：栈

柔光的暖阳◎ 2023-10-09 20:57 36阅读 0赞

#### 文章目录 ####

*  前言
 *  1.栈
 *   *  1.1 栈的概念及结构
     *  1.2 栈的实现
 *  2.栈功能的解析及实现
 *   *  2.1 栈的创建
     *  2.2 初始化
     *  2.3 入栈
     *  2.4 出栈
     *  2.5 检查栈是否为空
     *  2.6 获取栈顶元素
     *  2.7 栈中的有效元素个数
     *  2.8 销毁
 *  3.代码实现
 *   *  3.1 Stack.h
     *  3.2 Stack.c
     *  3.3 test.c
 *  4.总结

## 前言 ##

前面学习的一些结构都比较普通，今天就让我们来看一个比较特殊的结构——栈，它的特殊之处是后进先出，也就是后进来的数据先出去。

## 1.栈 ##

### 1.1 栈的概念及结构 ###

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

### 1.2 栈的实现 ###

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

## 2.栈功能的解析及实现 ##

### 2.1 栈的创建 ###

我们采用数组的形式进行实现。

typedef int DataType;
    typedef struct Stack
    {
        
    	DataType* data;
    	int top; //栈顶
    	int capacity;容量
    }Stack;

### 2.2 初始化 ###

将所有数据赋个初值。

void StackInit(Stack* ps)
    {
        
    	assert(ps);
    	ps->data = NULL;
    	ps->top = 0; //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
    	ps->capacity = 0;//栈的容量
    }

### 2.3 入栈 ###

入栈也就是要增加元素，那么首先需要做的就是判断容量够不够，不够的话就需要增容，然后再将元素放进去即可。

void StackPush(Stack* ps, DataType x)
    {
        
    	assert(ps);
    	//判断是否需要增容
    	if (ps->top == ps->capacity)
    	{
        
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
    		if (tmp == NULL)
    		{
        
    			return;
    		}
    		ps->data = tmp;
    		ps->capacity = newcapacity;
    	}
    	ps->data[ps->top] = x;
    	ps->top++;
    }

### 2.4 出栈 ###

出栈的话我们只能从栈顶出元素，不能从其他位置出。既然要删除元素，那么我们就需要判断栈中是否还有剩余元素，没有的话就不需要删除。这里我写了一种方式，不过后面还会写一个判断栈是否为空的函数，大家看个人喜好采用。

void StackPop(Stack* ps)
    {
        
    	assert(ps);
    	//assert(ps->top > 0);
    	assert(!StackEmpty(ps));
    	ps->top--;
    }

### 2.5 检查栈是否为空 ###

写的比较简洁，返回的是ps->top == 0，也就是如果条件成立，这个表达式就代表着true（也就是栈为空），如果不成立就代表着false（栈不为空）。

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

### 2.6 获取栈顶元素 ###

我们的top指向的是栈顶元素的下一个位置，所以在数组中最后一个元素也就是栈顶的元素位置是top - 1。

DataType StackTop(Stack* ps)
    {
        
    	assert(ps);
    	assert(!StackEmpty(ps));//判断是否为空
    	return ps->data[ps->top - 1];
    }

### 2.7 栈中的有效元素个数 ###

在创建栈哪里就提到了，top既指向栈顶元素的后一个位置，也代表着栈中的元素个数。

int StackSize(Stack* ps)
    {
        
    	assert(ps);
    	return ps->top;
    }

### 2.8 销毁 ###

动态开辟的空间在程序结束时都需要被回收，用来防止出现内存泄漏。

void StackDestroy(Stack* ps)
    {
        
    	ps->top = 0;
    	ps->capacity = 0;
    	free(ps->data);
    	ps->data = NULL;
    }

## 3.代码实现 ##

### 3.1 Stack.h ###

栈的创建以及各个函数声明。

#pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<stdbool.h>
    #include<stdlib.h>
    typedef int DataType;
    typedef struct Stack
    {
        
    	DataType* data;
    	int top;
    	int capacity;
    }Stack;
    
    // 初始化栈
    void StackInit(Stack* ps);
    
    // 入栈
    void StackPush(Stack* ps, DataType x);
    
    // 出栈
    void StackPop(Stack* ps);
    
    // 获取栈顶元素
    DataType StackTop(Stack* ps);
    
    // 获取栈中有效元素个数
    int StackSize(Stack* ps);
    
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
    bool StackEmpty(Stack* ps);
    
    // 销毁栈
    void StackDestroy(Stack* ps);

### 3.2 Stack.c ###

栈的各功能的函数。

#include"Stack.h"
    
    void StackInit(Stack* ps)
    {
        
    	assert(ps);
    	/*DataType* tmp = (DataType*)malloc(sizeof(DataType));
    	if (tmp == NULL)
    	{
    		return;
    	}*/
    
    	ps->data = NULL;
    	ps->top = 0;      //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
    	ps->capacity = 0;
    }
    
    void StackPush(Stack* ps, DataType x)
    {
        
    	assert(ps);
    	//判断是否需要增容
    	if (ps->top == ps->capacity)
    	{
        
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
    		if (tmp == NULL)
    		{
        
    			return;
    		}
    		ps->data = tmp;
    		ps->capacity = newcapacity;
    	}
    	ps->data[ps->top] = x;
    	ps->top++;
    }
    
    bool StackEmpty(Stack* ps)
    {
        
    	assert(ps);
    	return ps->top == 0;
    }
    
    void StackPop(Stack* ps)
    {
        
    	assert(ps);
    	//assert(ps->top > 0);
    	assert(!StackEmpty(ps));
    	ps->top--;
    }
    
    DataType StackTop(Stack* ps)
    {
        
    	assert(ps);
    	assert(!StackEmpty(ps));
    	return ps->data[ps->top - 1];
    }
    
    int StackSize(Stack* ps)
    {
        
    	assert(ps);
    	return ps->top;
    }
    
    void StackDestroy(Stack* ps)
    {
        
    	ps->top = 0;
    	ps->capacity = 0;
    	free(ps->data);
    	ps->data = NULL;
    }

### 3.3 test.c ###

用来测试实现的栈功能有没有问题。

#include"Stack.h"
    
    void test()
    {
        
    	Stack st;
    	StackInit(&st);//初始化
    
    	StackPush(&st, 1);//测试:入栈
    	StackPush(&st, 2);
    	StackPush(&st, 3);
    	StackPush(&st, 4);
    	while(!StackEmpty(&st))
    	{
        
    		printf("%d ", StackTop(&st));
    		StackPop(&st);
    	}
    	printf("\n");
    
    
    	StackPush(&st, 5);//入栈一些元素进行测试
    	StackPush(&st, 6);
    
    	StackPop(&st);//测试:中途出栈的效果,实际就是将6提前出栈
    
    	StackPush(&st, 7);
    	StackPush(&st, 8);
    	while (!StackEmpty(&st))
    	{
        
    		printf("%d ", StackTop(&st));
    		StackPop(&st);
    	}
    	printf("\n");
    
    
    	StackPush(&st, 1);//入栈一些数据进行测试
    	StackPush(&st, 2);
    	StackPush(&st, 3);
    	StackPush(&st, 4);
    
    	int sz = StackSize(&st);//测试:计算栈中元素个数
    	printf("%d\n", sz);
    
    	StackDestroy(&st);
    }
    int main()
    {
        
    	test();
    	return 0;
    }

## 4.总结 ##

单纯从代码实现角度来看，栈的实现还是比较简单的，因此可以不用在代码实现方面下太大的功夫，将更多的注意力转移到做题方面，感觉会有更好的效率性。  
  栈的讲解就先告一段落了，如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续深入学习数据结构的其他知识，开启新的篇章，那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励喔！！

[c56f6b3a6d16454d95b266406cc18a26.png]: https://img-blog.csdnimg.cn/c56f6b3a6d16454d95b266406cc18a26.png
[448eeccac9e24fa6ac23c2a519a13a40.png]: https://img-blog.csdnimg.cn/448eeccac9e24fa6ac23c2a519a13a40.png