栈的应用与基本操作
创作时间:
作者:
@小白创作中心
栈的应用与基本操作
引用
CSDN
1.
https://blog.csdn.net/m0_74918980/article/details/146051610
一.引言
栈（Stack）是一种常见的数据结构，它的特点是后进先出（LIFO, Last In First Out）。栈在计算机科学中有着广泛的应用，例如函数调用、表达式求值、括号匹配等。本文将详细介绍栈的基本操作，帮助读者深入理解栈的核心概念。
我们可以把栈想象成一个手枪弹夹，这种比喻非常形象且易于理解。弹夹的特点是后进先出（LIFO），也就是说，最后压入弹夹的子弹会最先被射出。
二.栈的基本概念
栈是一种线性数据结构，只允许在一端（称为栈顶）进行插入和删除操作。栈的核心操作包括：
- 入栈：将元素添加到栈顶。
- 出栈：移除栈顶元素。
- 获取栈顶元素：查看栈顶元素，但不移除。
- 判断栈是否为空：检查栈中是否有元素。
- 判断栈是否已满：检查栈是否达到最大容量（仅限顺序栈）。
三.栈的应用场景
因为栈作有着后进先出的特点，所以他在很多方面有着重要的应用，例如：
- 函数调用栈
在程序执行过程中，每次函数调用都会将当前函数的返回地址、局部变量等信息压入栈中。函数返回时，再从栈中弹出这些信息，恢复到调用前的状态，列如递归函数和树的前中后序遍历的应用。
- 括号匹配
栈可以用于检查代码中的括号是否匹配。例如，遍历代码字符串，遇到左括号时入栈，遇到右括号时出栈并检查是否匹配。
- 浏览器的前进与后退
浏览器的“后退”和“前进”功能可以通过两个栈实现：
- 一个栈存储已访问的页面（用于后退）。
- 另一个栈存储后退过程中弹出的页面（用于前进）。
- 撤销操作
这个功能再很多地方都有实现，比如文本编辑器的撤回操作，各种棋类游戏的悔棋操作等。
四.栈的实现方式
1.顺序栈
顺序栈的定义
顺序栈的核心是一个数组和一个栈顶指针。栈顶指针用于标记栈的当前位置，初始值为-1，表示栈为空。
// 定义栈结构
typedef struct Stack {
int data[MAX];
int top;
int bottom;
} stack;
初始化栈
初始化栈时，将栈顶指针top和栈底指针bottom设置为-1，表示栈为空。
// 初始化栈
void stackinit(stack* s) {
s->top = -1;
s->bottom = -1;
}
判断栈是否为空和判断是否满
在入栈出栈时调用方便。
// 判断栈是否为空
int isEmpty(stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(stack* s) {
return s->top == MAX - 1;
}
入栈和出栈
// 入栈
void push(stack* s, int data) {
if (isFull(s)) {
printf("栈已满，无法入栈\n");
return;
}
if (isEmpty(s)) {
s->bottom = 0;
}
s->top++;
s->data[s->top] = data;
}
// 出栈
int pop(stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法出栈\n");
return -1; // 返回一个错误值
}
int temp = s->data[s->top];
s->top--;
if (s->top == -1) {
s->bottom = -1;
}
return temp;
}
获取栈顶元素
// 获取栈顶元素
int peek(stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法获取栈顶元素\n");
return -1; // 返回一个错误值
}
return s->data[s->top];
}
获取当前栈的大小以及清空栈
清空时只需要将top和bottom重新设为-1就行
// 获取栈的当前大小
int stackSize(stack* s) {
return s->top + 1;
}
// 清空栈
void clearStack(stack* s) {
s->top = -1;
s->bottom = -1;
}
遍历栈
// 遍历栈
void show(stack* s) {
if (isEmpty(s)) {
printf("栈为空，没有数据\n");
return;
}
printf("栈内容（从栈顶到栈底）：");
for (int i = s->top; i >= s->bottom; i--) {
printf("%d ", s->data[i]);
}
printf("\n");
}
源代码
#include <stdio.h>
#define MAX 20
// 定义栈结构
typedef struct Stack {
int data[MAX];
int top;
int bottom;
} stack;
// 初始化栈
void stackinit(stack* s) {
s->top = -1;
s->bottom = -1;
}
// 判断栈是否为空
int isEmpty(stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(stack* s) {
return s->top == MAX - 1;
}
// 入栈
void push(stack* s, int data) {
if (isFull(s)) {
printf("栈已满，无法入栈\n");
return;
}
if (isEmpty(s)) {
s->bottom = 0;
}
s->top++;
s->data[s->top] = data;
}
// 出栈
int pop(stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法出栈\n");
return -1; // 返回一个错误值
}
int temp = s->data[s->top];
s->top--;
if (s->top == -1) {
s->bottom = -1;
}
return temp;
}
// 获取栈顶元素
int peek(stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法获取栈顶元素\n");
return -1; // 返回一个错误值
}
return s->data[s->top];
}
// 获取栈的当前大小
int stackSize(stack* s) {
return s->top + 1;
}
// 清空栈
void clearStack(stack* s) {
s->top = -1;
s->bottom = -1;
}
// 遍历栈
void show(stack* s) {
if (isEmpty(s)) {
printf("栈为空，没有数据\n");
return;
}
printf("栈内容（从栈顶到栈底）：");
for (int i = s->top; i >= s->bottom; i--) {
printf("%d ", s->data[i]);
}
printf("\n");
}
int main() {
stack s;
stackinit(&s);
// 测试入栈
push(&s, 5);
push(&s, 4);
push(&s, 3);
push(&s, 2);
// 测试获取栈顶元素
printf("栈顶元素: %d\n", peek(&s));
// 测试获取栈大小
printf("栈大小: %d\n", stackSize(&s));
// 测试出栈
printf("出栈元素: %d\n", pop(&s));
// 测试遍历栈
show(&s);
// 测试清空栈
clearStack(&s);
printf("清空栈后，栈是否为空: %s\n", isEmpty(&s) ? "是" : "否");
return 0;
}
2.链栈
链栈的基本操作与顺序栈类似，只是换成了指针的方式来操作，这里就不过多赘述，直接将源代码展示出来。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
typedef struct
{
Node* top;
}LinkStack;
void init(LinkStack* L){
L->top=NULL;
}
int isEmpty(LinkStack* L){
return L->top==NULL;
}
//入栈
void push(LinkStack* L,int data){
Node* newnode=(Node*)malloc(sizeof(Node));
if (!newnode) {
printf("内存分配失败\n");
return;
}
newnode->data=data;
newnode->next=L->top;
L->top=newnode;
}
//出栈
int pop(LinkStack* L){
if(isEmpty(L)){
printf("栈为空，无法出栈\n");
return -1;
}
int value;
Node* temp=L->top;
value=temp->data;
L->top=temp->next;
free(temp);
return value;
}
//获取栈顶元素
int peek(LinkStack* L){
if(isEmpty(L)){
printf("栈为空，无法出栈\n");
return -1;
}
return L->top->data;
}
// 打印栈内容
void show(LinkStack* L){
Node* temp=L->top;
while (temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
if(isEmpty(L)){
printf("NULl\n");
}
}
int main(int argc, char const *argv[])
{
LinkStack L;
init(&L);
push(&L, 10);
push(&L, 20);
push(&L, 30);
printf("栈内容: ");
show(&L);
printf("栈顶元素: %d\n", peek(&L));
printf("出栈元素: %d\n", pop(&L));
printf("栈内容: ");
show(&L);
return 0;
}
3.顺序栈和链栈的对比
以下是顺序栈和链栈的对比表格，从多个方面对两者进行了详细的比较：
特性 | 顺序栈 | 链栈 |
|---|---|---|
存储结构 | 基于数组，连续内存空间。 | 基于链表，动态分配内存。 |
空间开销 | 无额外指针开销，空间利用率高。 | 每个节点需要额外指针空间，空间利用率较低。 |
容量限制 | 容量固定，需预先确定大小，超出会栈溢出。 | 容量动态变化，无固定限制。 |
插入/删除效率 | 入栈和出栈操作的时间复杂度为 O(1)。 | 入栈和出栈操作的时间复杂度为 O(1)。 |
访问效率 | 连续内存访问，对 CPU 缓存友好，访问效率高。 | 非连续内存访问，访问效率较低。 |
动态扩容 | 不支持动态扩容（需重新分配内存并复制数据，时间复杂度为 O(n)）。 | 支持动态扩容，无需预先分配固定空间。 |
内存管理 | 无需频繁分配和释放内存，内存管理简单。 | 频繁分配和释放内存，可能导致内存碎片。 |
实现复杂度 | 实现简单，代码清晰。 | 实现较复杂，需处理指针和动态内存分配。 |
适用场景 | 栈大小固定或可预估，对性能要求高。 | 栈大小不确定或动态变化，需要频繁插入和删除。 |
典型应用 | 函数调用栈、表达式求值、括号匹配。 | 撤销操作、浏览器的前进与后退、动态变化的栈场景。 |
五.总结
栈是一种简单但功能强大的数据结构，广泛应用于计算机科学的各个领域。通过掌握栈的基本操作和应用场景，可以更好地解决实际问题。
希望本文能帮助你深入理解栈的核心概念。
热门推荐
国际观察丨德国联盟党胜选后依旧面临政治难题
价格大降，最低只要1块钱！不少网友直呼心动……
手搖飲市場新未來：健康與創新如何引領潮流
进阶高手：关于房室传导阻滞 这篇文章不可不看
樱桃树的种植与管理
腌制咸菜，如何制作美味可口的咸菜（家庭必备腌制技巧）
汉语拼音基础知识
【以案释法】网购珍珠A，收货时变珍珠B，算欺诈还是发错货？
儒家思想中的无为原则及其现代意义
读书app界面设计，探索现代读书应用界面设计趋势
移动硬盘数据恢复完整教程：5种实用方法帮你找回丢失的数据
怎么把EXCEL所有表格式弄成一样
针灸：传统医学瑰宝的前世今生
摩卡壶咖啡制作过程详解：从选购到使用全攻略
闰六月是什么意思？闰六月是哪几年？
中药浓淡药效有关系吗
如何选择最适合你的单元测试框架？【详尽指南】
中国宽体大飞机国产化率突破90%震撼全球 C929横空出世
如何分析一个小区的物业服务质量？这种分析对居民满意度有何影响？
全红婵：从湛江农家女到奥运冠军的逆袭之路
佳能打印机黄灯一直闪无法打印？一文详解故障排查与预防措施
关于牵引车不同技术路线的TCO对比分析及预测
项目经理如何晋升
袁世凯的“袁大头”银元，为什么成了市场上最具价值的货币？
如何选择适合的网络协议和配置以优化服务器的网络性能？
90后自主创业成功例子
从质量到健康：卫生巾行业的信任重建
第四套人民币1980年1角稀有冠荧光版：收藏潜力之星
信息论基础：理论与应用的全面解析
公募REITs发行大提速，逼近1500亿元大关