数据结构与算法 | 栈

栈

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端为栈顶，另一端为栈底。栈中元素遵循先进后出的原则
假设我们依次将1， 2， 3， 4压入栈中



当我们再全部出栈时，就从1，2，3，4变成了4，3，2，1

这就是栈的先进后出的规则，知晓了原理，下一步就开始实现。
这里我们结合栈的特性，选用顺序表来实现更优一些，而下期的队列则用链表实现

数据结构

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

实现的接口

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, DataType data);
// 出栈 
void StackPop(Stack* ps);// 获取栈顶元素 
DataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零(1)，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
//确认是否需要扩容
void ChackCapacity(Stack* ps);

初始化栈

void StackInit(Stack* ps)
{ps->data = (DataType*)malloc(STACKSIZE * sizeof(DataType));ps->top = 0;ps->capacity = STACKSIZE;
}

检查栈是否扩容

void ChackCapacity(Stack * ps)
{if (ps->top >= ps->capacity){ps->capacity *= 2;ps->data = (DataType*)realloc(ps->data, ps->capacity * sizeof(DataType));}
}

我们只需要判断栈顶是否超过当前容量，超过后重新分配给多空间即可

入栈

void StackPush(Stack* ps, DataType data)
{ChackCapacity(ps);ps->data[ps->top++] = data;
}

每次将数据放在栈顶的位置，再将栈顶往后推

出栈

void StackPop(Stack* ps)
{if (0 == ps->top)return;ps->top--;
}

出栈只需要把栈顶指针回退一格即可，这样我们就不能通过栈顶来访问出栈的位置

获取栈顶元素

DataType StackTop(Stack* ps)
{if (0 == ps->top)return (DataType)0;return ps->data[ps->top - 1];
}

因为我们的栈顶时刻处于栈顶元素的后一个，所以只需要返回栈顶的前一个位置即可

获取栈中有效元素个数

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

直接返回栈顶的位置

检测栈是否为空

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

当栈顶处于栈底的位置时，说明栈为空

销毁栈

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

完整代码
头文件

#include
#include
#include
#define _CRT_SECURE_NO_WARNINGS
#define STACKSIZE 10
typedef int DataType;
typedef struct Stack
{DataType* data;int top;		// 栈顶int capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, DataType data);
// 出栈 
void StackPop(Stack* ps);// 获取栈顶元素 
DataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零(1)，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
//确认是否需要扩容
void ChackCapacity(Stack* ps);

函数实现

#include"Stack.h"void ChackCapacity(Stack* ps)
{if (ps->top >= ps->capacity){ps->capacity *= 2;ps->data = (DataType*)realloc(ps->data, ps->capacity * sizeof(DataType));}
}
void StackInit(Stack* ps)
{ps->data = (DataType*)malloc(STACKSIZE * sizeof(DataType));ps->top = 0;ps->capacity = STACKSIZE;
}// 入栈 
void StackPush(Stack* ps, DataType data)
{ChackCapacity(ps);ps->data[ps->top++] = data;
}// 出栈 
void StackPop(Stack* ps)
{if (0 == ps->top)return;ps->top--;
}// 获取栈顶元素 
DataType StackTop(Stack* ps)
{if (0 == ps->top)return (DataType)0;return ps->data[ps->top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{return ps->top;
}// 检测栈是否为空，如果为空返回非零(1)，如果不为空返回0 
int StackEmpty(Stack* ps)
{return ps->top == 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{free(ps->data);ps->data = NULL;ps->top = 0;ps->capacity = 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！