专业做网站网络,域名备案的网站建设方案书模板,生活服务手机网站开发,网站域名重定向怎么做栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO#xff08;Last In First Out#xff09;的原则。 压栈#…栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈的定义
typedef int STDataType;
typedef struct Stack
{STDataType* _a;//数组int _top; // 栈顶,类似顺序表中的_sizeint _capacity; // 容量
}Stack;
对栈的操作
栈初始化
_top可以初始化为0此时栈顶元素是_top-1的位置
_top也可以初始化为1此时栈顶元素就是_top的位置
初始化为0 初始化为1
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-_a NULL;ps-_capacity 0;ps-_top 0;
}
压栈入栈 // 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//扩容if (ps-_capacity ps-_top){int newcapacity ps-_capacity 0 ? 4 : 2 * (ps-_capacity);STDataType* tmp (STDataType*)realloc(ps-_a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}ps-_a tmp;ps-_capacity newcapacity;}ps-_a[ps-_top] data;
}
出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-_top--;
}
取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps-_a[ps-_top-1];
}
判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-_top 0;
}
栈的长度
_top初始化为0此时的_top的大小刚好就是栈的长度
int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}
栈销毁
void StackDestroy(Stack* ps)
{assert(ps);ps-_capacity ps-_top 0;free(ps-_a);ps-_a NULL;
}
完整总代码
头文件
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;//数组int _top; // 栈顶,类似顺序表中的_sizeint _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
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);函数定义
#includeStack.h
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-_a NULL;ps-_capacity 0;ps-_top 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//扩容if (ps-_capacity ps-_top){int newcapacity ps-_capacity 0 ? 4 : 2 * (ps-_capacity);STDataType* tmp (STDataType*)realloc(ps-_a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}ps-_a tmp;ps-_capacity newcapacity;}ps-_a[ps-_top] data;
}
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps-_a[ps-_top-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-_top 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);ps-_capacity ps-_top 0;free(ps-_a);ps-_a NULL;
}
测试
#includeStack.h
void test()
{Stack s;StackInit(s);StackPush(s, 1);StackPush(s, 2);StackPush(s, 3);StackPush(s, 4);while (StackSize(s)0){printf(%d , StackTop(s));StackPop(s);}StackDestroy(s);
}
int main()
{test();return 0;
}欢迎各位一起学习交流~
