栈的顺序存储及实现(二)
程序员文章站
2022-06-05 13:33:53
...
栈的介绍
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又被称为后进先出(LastIn First Out)的线性表,简称LIOF结构。
首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。
代码实现
栈一般的实现都是用顺序存储结构进行实现的,上次我们在栈的顺序存储结构及实现(一)采用的数组进行实现,但是数组有个瓶颈就是固定了栈的长度,这次我们才采用动态获取内存空间,当压栈时如果栈满进行动态的扩充容量,进行栈的实现。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 5
#define STACK_INCREMENT 5
typedef int Status;
typedef int EleType;
typedef struct SeqStack
{
EleType* top;//栈顶指针
EleType* base;//栈底指针
int stackSize;//栈容量
}SeqStack;
//初始化栈
Status InitStack(SeqStack* stack)
{
//开辟空间
stack->base = stack->top = (EleType*)malloc(STACK_INIT_SIZE*sizeof(EleType));
if (!stack->base)
{
exit(0);
}
return OK;
}
/*
清空栈
*/
Status ClearStack(SeqStack* stack) {
if (NULL == stack) {
return ERROR;
}
//清空栈 实质上是忽略栈中数据,可以再次使用内存单元
stack->top = stack->base;
return OK;
}
/*
销毁栈
*/
Status DestroyStack(SeqStack* stack)
{
if (NULL == stack) {
return ERROR;
}
//销毁栈 是释放栈在内存中占用的空间资源
if (!stack->base)
{
free(stack->base);
}
stack->top = stack->base = NULL;
stack->stackSize = 0;
return OK;
}
//获取栈长度(栈中元素个数)
int LengthStack(SeqStack stack)
{
return stack.top - stack.base;
}
//压栈
Status push(SeqStack* stack,EleType e)
{
if (stack == NULL)
{
return ERROR;
}
//压栈之前检测容量是否足够
if (stack->top - stack->base == stack->stackSize)
{
//超出容量 进行扩容,使用realloc函数,会拷贝原内存内容
stack->base = (SeqStack*)realloc(stack->base, stack->stackSize+STACK_INCREMENT);
if (!stack->base)
{
exit(0);
}
stack->top = stack->base + stack->stackSize;
stack->stackSize += STACK_INCREMENT;
}
*stack->top = e;
stack->top++;
return OK;
}
//弹栈
Status pop(SeqStack* stack, EleType *e)
{
if (stack == NULL || e == NULL)
{
return ERROR;
}
//空栈
if (stack->top == stack->base)
{
return ERROR;
}
*stack->top--;
*e = *stack->top;
return OK;
}
/*
判断栈是否为空
*/
int IsEmptyStack(SeqStack* stack) {
if (NULL == stack) {
return ERROR;
}
if (stack->top == stack->base) {
return TRUE;
}
return FALSE;
}
/*
获取栈顶元素
*/
Status GetTop(SeqStack* stack, EleType *e) {
if (NULL == stack) {
return ERROR;
}
*e = *(stack->top - 1);
return OK;
}
/*
从栈顶向下展示元素值
*/
Status ShowStack(SeqStack* stack) {
if (NULL == stack || stack->top == stack->base) {
return ERROR;
}
EleType *top = stack->top;
while (top != stack->base)
{
top--;
printf("%d\n", *top);
}
return OK;
}
int main(int argc, char *argv[])
{
SeqStack stack;//创建顺序栈
InitStack(&stack);//初始化
printf("压入元素5,4,3,2,1\n");
push(&stack, 5);
push(&stack, 4);
push(&stack, 3);
push(&stack, 2);
push(&stack, 1);
puts("栈元素展示:");
ShowStack(&stack);
puts("弹出2个元素后");
puts("栈元素展示:");
EleType e1, e2,e3;
pop(&stack, &e1);
pop(&stack, &e2);
ShowStack(&stack);
printf("弹出元素为:%d,%d\n", e1, e2);
//测试是否动态扩充容量
push(&stack,8);
push(&stack,9);
push(&stack,10);
printf("压入元素8,9,10\n");
puts("栈元素展示:");
ShowStack(&stack);
GetTop(&stack, &e3);
printf("栈顶元素为:%d\n", e3);
DestroyStack(&stack);
return 0;
}
运行结果
推荐阅读
-
PHP实现UTF8二进制及明文字符串的转化功能示例
-
PHP实现按之字形顺序打印二叉树的方法
-
jquery 实现二级/三级/多级联动菜单的思路及代码
-
SpringBoot实现本地存储文件上传及提供HTTP访问服务的方法
-
go语言实现顺序存储的栈
-
Go语言实现顺序存储的线性表实例
-
JavaScript实现二叉树定义、遍历及查找的方法详解
-
《全栈营销之如何制作个人博客》之二:php环境安装及个人博客后台搭建 让你的博客跑起来
-
作业笔记:基于二次插值的Wolfe-Powell非精确线搜索算法及Python代码实现
-
用一张表来存储数据状态,并且可以进行多状态精确查询;使用二进制来表示数据状态,并且是可以无顺序的状态;解决使用中间表来存储数据的多状态;数据状态还可以这么玩;