提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
栈(Stack)是计算机科学中一种常见的数据结构,它是一种线性数据结构,具有特定的添加和删除元素的方式,遵循"先进后出"(Last In, First Out,LIFO)原则。栈通常用于管理函数调用、表达式求值、内存管理等多个计算机科学领域。
提示:以下是本篇文章正文内容,下面案例可供参考
一、栈
栈是一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守**先进后出LIFO(Last In First Out)**的原则。
压栈:栈的插入操作叫做进行入栈、进栈、压栈,入数据在栈顶;
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
栈的实现一般可以使用数组或者链表,相对而言数组的结构实现更优一些,因为数组在尾上插数据的代价比较小。
二、C语言实现
1.声明代码
代码如下(示例):
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDatatype;
// 数组栈,数组尾部为栈顶,数组头为栈底
typedef struct Stack
{
STDatatype* a;
int capacity;
int top;
}ST;
void StackInit(ST* ps); //初始化栈
void StackDestroy(ST* ps); // 销毁栈
void StackPush(ST* ps, STDatatype x); //入栈
void StackPop(ST* ps); //出栈
STDatatype StackTop(ST* ps); //获取栈顶元素
bool StackEmpty(ST* ps); // 判断栈是否为空
int StackSize(ST* ps); //栈中元素个数
2.实现增删查改代码
代码如下(示例):
#include "Stack.h"
void StackInit(ST* ps)
{
assert(ps); //断言检查
ps->a = (ST*)malloc(sizeof(ST) * 4); //开辟空间
if (ps->a == NULL) //空间申请失败
{
perror("malloc fail....");
exit(-1);
}
ps->capacity = 0;
ps->top = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps); //释放空间
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackPush(ST* ps, STDatatype x) //入栈
{
assert(ps);
if (ps->top+1 == ps->capacity) // 如果空间已经满了
{
STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype)); //扩容
if (ps->a == NULL)
{
perror("malloc fail...");
exit(-1);
}
ps->a = tmp; //ps要指向新开辟的空间tmp
ps->capacity *= 2; // ps的容量变为原来的2倍
}
ps->top++;
ps->a[ps->top] = x;
}
void StackPop(ST* ps) //出栈
{
assert(ps);
ps->top--; //指针前移
}
STDatatype StackTop(ST* ps) //获取栈顶元素
{
assert(ps);
assert(!StackEmpty(ps)); //断言栈不为空
return ps->a[ps->top-1]; //注意:栈顶元素为top的前一个元素
}
bool StackEmpty(ST* ps) // 判断栈是否为空
{
assert(ps);
if (ps->top == 0)
{
return true;
}
else
{
return false;
}
}
int StackSize(ST* ps) //栈中元素个数
{
assert(ps);
return ps->top; //top为最后一个数据的下一个位置
}
3.测试代码
代码如下(示例):文章来源:https://www.toymoban.com/news/detail-676759.html
#include "Stack.h"
//栈的实现一般可以使用数组或者链表,相对而言数组的结构实现更优一些,
// 因为数组在尾上插数据的代价比较小。
void Stack_Test1()
{
ST st;
StackInit(&st); //初始化结构体,要把结构体的地址传过去
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
int size = StackSize(&st);
printf("st's size:%d", size);
StackDestroy(&st);
}
int main()
{
Stack_Test1();
return 0;
}
总结
栈适用于需要后进先出操作的情况,例如函数调用和操作历史记录。文章来源地址https://www.toymoban.com/news/detail-676759.html
到了这里,关于C++数据结构学习——栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!