赞
踩
栈是一种基本的抽象数据类型,具有后进先出的特点。在栈这种数据结构中,元素只能在一端进行插入和删除操作,这一端被称为栈顶(Top),而另一端则称为栈底(Bottom)。
栈的存储结构主要有两种实现方式:
栈的基本操作包括:
栈的应用场景包括但不限于:
综上所述,栈是一种非常有用和广泛应用的数据结构,它以其独特的后进先出的数据特点,在计算机科学中扮演着重要的角色。
对比链栈,顺序栈的快速是更有优势的,所以我们来实现顺序栈。
首先创建三个文件:
// 支持动态增长的栈
typedef int STDataType;//对数据类型重命名,方便后期修改类型
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;//定义结构同时重命名
需要注意的是:top的指向应该始终保持一致性
1.如果top指向栈顶元素,初始不能为0,应该指向-1
2.如果top初始为0,其应该指向栈顶元素的下一个元素
这里我们统一初始化为0.
void StackInit(Stack* ps)
{
ps->a = NULL;
ps->capacity = ps->top = 0;
}
先判断空间是否足够,然后直接插入到top位置即可
// 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->capacity == ps->top)//判断是否需要扩容 { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc"); exit(1); } ps->a = tmp; ps->capacity = newcapacity; } //确定空间足够之后再插入数据 ps->a[ps->top] = data; ps->top++; }
直接top–即可。
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top);
ps->top--;
}
直接返回top-1位置的数据。
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top);
return ps->a[ps->top - 1];
}
直接返回top。
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
返回top==0的结果,因为当top为0时栈为空。
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{
return ps->top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
#include<stdio.h> #include<stdlib.h> #include<assert.h> // 支持动态增长的栈 typedef int STDataType;//对数据类型重命名,方便后期修改类型 typedef struct Stack { STDataType* a; int top; // 栈顶 int capacity; // 容量 }Stack;//定义结构同时重命名 // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
#include"Stack.h" // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->capacity == ps->top) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc"); exit(1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = data; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top); ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top); return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps) { return ps->top == 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。