安徽国华建设工程项目管理有限公司网站,做qq图片的网站吗,做网站前端有前途么,中国反钓鱼网站联盟1.栈的概念 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO#xff08;Last In First Out#xff09;的原则。 压栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶
2.栈结构的特点
后进先出LIFO栈的最显著特点是后进先出的数据访问方式。也就是说最后添加到栈中的元素会首先被移除而最先添加的元素会被保留在栈的底部直到后续被移除。限制性访问栈通常只允许在栈顶进行操作包括添加元素入栈和移除元素出栈。这种限制性访问确保了数据的一致性和有效性因为只有最顶端的元素才是可见和可访问的。基于顺序存储或链式存储栈可以基于顺序存储如数组和顺序表或链式存储如链表实现。在顺序存储中栈的元素被连续存储在内存中的一个连续区域并且栈顶的位置可以随着入栈和出栈操作进行动态调整。而在链式存储中每个元素都有一个指向下一个元素的指针形成了一个链式结构。常见应用栈在计算机科学中有着广泛的应用包括函数调用栈、表达式求值、语法分析、内存管理等方面。在算法和数据结构中栈也是解决许多问题的重要工具。内存管理栈内存储在程序的运行时栈空间中由编译器或解释器负责管理。入栈和出栈操作通常比较高效并且不会导致内存碎片化。 总的来说栈是一种简单但功能强大的数据结构它的后进先出特性使其在许多领域都有着重要的应用。 栈结构通常是用顺序表来实现的如果学会了顺序表和链表再来实现栈结构就行显得简单的多。
3.栈的实现
3.1头文件的声明
#pragma once
#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);// 获取栈中有效元素个数
int StackEmpty(Stack* ps);// 检测栈是否为空
void StackDestroy(Stack* ps);// 销毁栈
3.2初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-_a NULL;ps-_top ps-_capacity 0;
}
3.3入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-_top ps-_capacity){int dt ps-_capacity 0 ? 4 : ps-_capacity * 2;STDataType* pnew (STDataType*)realloc(ps-_a, sizeof(STDataType) * dt);//申请栈空间assert(pnew);ps-_a pnew;ps-_capacity dt;//更新空间大小}ps-_a[ps-_top] data;ps-_top;
}
3.4出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-_top);ps-_top--;
}
3.5获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-_top);ps-_top--;return ps-_a[ps-_top];
}
3.6判空
// 检测栈是否为空如果为空返回0结果如果不为空返回非零
int StackEmpty(Stack* ps)
{assert(ps);return ps-_top 0 ? 1 : 0;
}
3.7销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-_a);ps-_a NULL;ps-_top ps-_capacity 0;
}
4.原码
Stack.h
#pragma once
#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 dt ps-_capacity 0 ? 4 : ps-_capacity * 2;STDataType* pnew (STDataType*)realloc(ps-_a, sizeof(STDataType) * dt);//申请栈空间assert(pnew);ps-_a pnew;ps-_capacity dt;//更新空间大小}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);ps-_top--;return ps-_a[ps-_top];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回0结果如果不为空返回非零
int StackEmpty(Stack* ps)
{assert(ps);return ps-_top 0 ? 1 : 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-_a);ps-_a NULL;ps-_top ps-_capacity 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h
int main()
{Stack pst;Stack* pr pst;// 初始化栈 StackInit(pr);StackPush(pr, 1);StackPush(pr, 2);StackPush(pr, 3);StackPush(pr, 4);StackPush(pr, 5);StackPush(pr, 6);StackPop(pr);while (!StackEmpty(pr)){printf(%d , StackTop(pr));}printf(\n%d, StackSize(pr));StackDestroy(pr);return 0;
}
