文章目录
1.栈的概念及结构2.栈的实现2.1初始化2.2入栈2.3出栈2.4栈顶元素2.5栈中有效元素个数2.6检测栈是否为空2.7销毁栈2.8栈的打印
今天学习一种新的数据结构——栈
1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
typedef int StackDataType;
//动态
typedef struct Stack
{
StackDataType* arr;//数组实现
int top;//栈顶，有效元素的下一个
int capacity;//数组容量
}Stack;
2.栈的实现
栈这种数据结构的特点就是后进先出，由于它的特性，它的使用方法也就不像链表那样麻烦。基本使用如下：
2.1初始化
//初始化
void StackInit(Stack* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = 0;
ps->top = 0;
}
2.2入栈
入栈前，应检查数组的大小。若数组满了，应进行扩容。
//入栈
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
//检查容量
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//扩容
StackDataType* tmp = (StackDataType*)realloc(ps->arr, sizeof(StackDataType) * newcapacity);
if (!tmp)
{
perror("realloc");
return;
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
//数据入栈
ps->arr[ps->top] = x;
ps->top++;
}
2.3出栈
由于我们使用的是数组，所以出栈就非常简单，只需将栈顶下移即可。
//出栈
void StackPop(Stack* ps)
{
assert(ps);
//栈中得有元素
assert(ps->top);
//出栈
ps->top--;
}
2.4栈顶元素
//栈顶元素
StackDataType StackTopElement(Stack* ps)
{
assert(ps);
assert(ps->top);
return ps->arr[ps->top - 1];
}
2.5栈中有效元素个数
由于数组下标从0开始，我们的栈顶指向的是当前元素的下一个位置；因此，直接返回栈顶即可。
//有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
2.6检测栈是否为空
如果为空返回非零结果，如果不为空返回0
//是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
2.7销毁栈
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = 0;
ps->top = 0;
}
2.8栈的打印
由于栈的特性，它的打印方式和数组不同。它是先获取栈顶元素打印，然后出栈。
int main()
{
Stack stack;
StackInit(&stack);
StackPush(&stack, 1);
StackPush(&stack, 2);
StackPush(&stack, 3);
StackPush(&stack, 4);
StackPush(&stack, 5);
while (!StackEmpty(&stack))
{
int top = StackTopElement(&stack);
printf("%d ", top);
StackPop(&stack);
}
return 0;
}
相关阅读
您阅读本篇文章共花了：
发表评论