下载类网站 建设方案,樟木头网站仿做,wordpress好用的插件推荐,怎么做卖衣服网站#x1f493; 博客主页#xff1a;倔强的石头的CSDN主页 #x1f4dd;Gitee主页#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏#xff1a;《数据结构与算法》 期待您的关注 目录 一、引言 #x1f384;栈#xff08;Stack#xff09;是什么#xff1f; #x1… 博客主页倔强的石头的CSDN主页 Gitee主页倔强的石头的gitee主页 ⏩ 文章专栏《数据结构与算法》 期待您的关注 目录 一、引言 栈Stack是什么 为什么使用数组实现栈
二、定义栈结构
栈的结构
栈顶位置的指向
三、实现栈的基本操作
初始化
销毁
入栈
出栈
查看栈顶元素
对栈判空
获取有效数据个数
四、使用数组实现栈的C语言代码
stack.h 栈的头文件
stack.c 栈的实现源文件
test.c 主函数测试文件
测试结果
五、栈的应用
六、总结 一、引言 栈Stack是什么 栈是一种后进先出LIFO, Last In First Out的数据结构。栈是一种只能在一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶top另一端称为栈底bottom。栈中没有元素时称为空栈。栈的基本操作包括push入栈、pop出栈、peek查看栈顶元素和isEmpty判断栈是否为空等。
为什么使用数组实现栈 数组是一种线性数据结构能够连续存储数据且通过索引可以方便地访问任意位置的元素。因为栈只在栈顶增删所以基于数组实现既避免了插入需要移动数据的劣势又保持了数组访问数据的优势可以实现高效的栈操作。 二、定义栈结构
栈的结构 指向数组的指针动态开辟的空间标记栈顶位置的变量 top标记栈的大小的变量 capacity // 支持动态增长的栈
typedef int STDataType;//对数据类型重命名方便后期修改类型
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;//定义结构同时重命名 栈顶位置的指向
需要注意的是top的指向应该始终保持一致性 1.如果top指向栈顶元素初始不能为0应该指向-1
2.如果top初始为0其应该指向栈顶元素的下一个元素 对应的判定栈满和栈空有所不同 三、实现栈的基本操作
初始化 对形参判空数组指针初始指向空top和capacity初始化为0这里top指向的是栈顶元素的下一个位置 // 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}销毁 对形参判空释放数组空间数组指针指向空top和capacity改为0 // 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
} 入栈 判空 判断是否需要扩容top和capacity相等 扩容步骤: 空间二倍增长 更新数组指针和容量 数据插入到top位置top位置 // 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps-top ps-capacity){int newcapa ps-capacity 0 ? 4 : 2 * (ps-capacity);STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapa);if (tmp NULL){perror(realloc\n);exit(1);}ps-a tmp;ps-capacity newcapa;}//确定空间足够之后再插入数据ps-a[ps-top] data;ps-top;
}出栈 对形参判空对栈判空top-- 该方法对于栈只存在一个元素的情况也可以正确处理 // 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top);ps-top--;
} 注意 即使函数只有一两条语句也还是建议封装成函数这样可以提高程序的可维护性和可读性 查看栈顶元素 对形参判空对栈判空返回top前一个位置的元素 // 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top);return ps-a[ps-top-1];
}对栈判空 对形参判空返回top0的结果因为这里top指向的是栈顶元素的下一个元素所以栈空时top0 // 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
} 获取有效数据个数 对形参判空返回top top对应的下标是栈顶的下一个元素top就是元素的个数 // 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
} 四、使用数组实现栈的C语言代码
stack.h 栈的头文件
#includestdio.h
#includestdlib.h
#includeassert.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); stack.c 栈的实现源文件
#includestack.h// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps-top ps-capacity){int newcapa ps-capacity 0 ? 4 : 2 * (ps-capacity);STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapa);if (tmp NULL){perror(realloc\n);exit(1);}ps-a tmp;ps-capacity newcapa;}//确定空间足够之后再插入数据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)
{assert(ps);return ps-top 0;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
} test.c 主函数测试文件
#includestack.hvoid test1()
{Stack st ;StackInit(st);if (StackEmpty(st)){printf(栈空\n);}else{printf(栈非空\n);}StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);if (StackEmpty(st)){printf(栈空\n);}else{printf(栈非空\n);}printf(栈中元素个数%d\n, StackSize(st));printf(%d\n, StackTop(st));StackPop(st);printf(%d\n, StackTop(st));StackPop(st);printf(%d\n, StackTop(st));StackPop(st);printf(%d\n, StackTop(st));StackPop(st);if (StackEmpty(st)){printf(栈空\n);}else{printf(栈非空\n);}StackDestroy(st);}int main()
{test1();return 0;
}
测试结果 五、栈的应用
函数调用栈在程序执行过程中函数调用是通过栈来实现的。每个函数调用时其返回地址、局部变量和参数等信息都会被压入栈中当函数返回时这些信息会被弹出栈。表达式求值在编译器中表达式求值通常使用栈来实现。例如在解析算术表达式时可以使用两个栈一个用于存储操作数另一个用于存储操作符。浏览器历史记录浏览器的“前进”和“后退”功能通常使用栈来实现。用户浏览的网页会被压入栈中当用户点击“后退”按钮时会从栈中弹出并显示上一个网页。撤销操作在许多图形编辑器和文本编辑器中撤销操作通常使用栈来实现。每次编辑操作如剪切、复制、粘贴等都会被压入一个撤销栈中当用户点击“撤销”按钮时会从栈中弹出并执行相反的操作以撤销上一次编辑。 六、总结
使用数组实现栈是一种简单且高效的方法能够充分利用数组的特性来实现栈的基本操作。在实际应用中栈具有广泛的应用场景如函数调用栈、浏览器的前进后退功能以及表达式求值等。
