（数据结构）栈讲解和栈实现

清疚 2023-02-16 04:23 13阅读 0赞

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

举几个例子更好的理解栈：  
1.羽毛球桶，把羽毛球一个一个放进去，先取出来的一定是最后放进去的。  
2.吃进去，吐出来（这个例子可能不太恰当，但是很直观）

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

栈的结构包括定长的静态栈和支持动态增长的栈。一般使用后者较多。以下是动态增长栈的实现：  
**Stack.h**

#pragma once
    
    typedef int SDataType;
    
    typedef struct Stack
    {
        
    	SDataType* array;
    	int capacity;
    	int size;//栈中元素的个数 栈顶
    }Stack;
    
    void StackInit(Stack* ps);
    //入栈：尾插
    void StackPush(Stack* ps, SDataType data);
    //出栈：尾删
    void StackPop(Stack* ps);
    //获取栈顶元素
    SDataType StackTop(Stack* ps);
    //获取栈中有效元素个数
    int StackSize(Stack* ps);
    //检测是否为空
    int StackEmpty(Stack* ps);
    //销毁
    void StackDestroy(Stack* ps);

**Stack.c**

#include "Stack.h"
    #include <malloc.h>
    #include <assert.h>
    #include <stdio.h>
    #include <string.h>
    
    void StackInit(Stack* ps)
    {
        
    	assert(ps);
    	ps->array = (SDataType*)malloc(sizeof(SDataType)* 10);
    	if (NULL == ps->array)
    	{
        
    		assert(0);
    		return;
    	}
    	ps->capacity = 10;
    	ps->size = 0;
    }
    void CheckCapacity(Stack* ps)
    {
        
    	assert(ps);
    	if (ps->size == ps->capacity)
    	{
        
    		//1.开辟新空间
    		SDataType* temp = (SDataType*)malloc(sizeof(SDataType)*ps->size * 2);
    		if (temp == NULL)
    		{
        
    			assert(0);
    			return;
    		}
    		//2.拷贝元素
    		memcpy(temp, ps->array, sizeof(SDataType)*ps->size);
    		//3.释放旧空间
    		free(ps->array);
    		ps->array = temp;
    		ps->capacity *= 2;
    	}
    }
    //入栈：尾插
    void StackPush(Stack* ps, SDataType data)
    {
        
    	assert(ps);
    	CheckCapacity(ps);
    	ps->array[ps->size++] = data;
    }
    //出栈：尾删
    void StackPop(Stack* ps)
    {
        
    	if (StackEmpty(ps))
    		return;
    	ps->size--;
    }
    //获取栈顶元素
    SDataType StackTop(Stack* ps)
    {
        
    	assert(!StackEmpty(ps));
    	return ps->array[ps->size - 1];
    }
    //获取栈中有效元素个数
    int StackSize(Stack* ps)
    {
        
    	assert(ps);
    	return ps->size;
    }
    //检测是否为空
    int StackEmpty(Stack* ps)
    {
        
    	assert(ps);
    	return ps->size == 0;
    }
    //销毁
    void StackDestroy(Stack* ps)
    {
        
    	assert(ps);
    	free(ps->array);
    	ps->array = NULL;
    	ps->capacity = 0;
    	ps->size = 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200608103007458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[20200608103147111.png]: https://img-blog.csdnimg.cn/20200608103147111.png