查找网站注册时间,微信公众号怎么做网站,网站优化有哪些,百度知道合伙人答题兼职1.栈的概念及结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈#xff1a;栈的插入操作叫做进栈/压栈/入栈#…1.栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据也在栈顶。 此图来源与网络 这里我们可以比作肉串,我们先把肉串好,后串上的肉,是先吃的.
2.栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 这里我就用数组来实现一下,感兴趣的可以用链表实现一下
个人感觉这个的写法比较类似顺序表
我们先创建栈,然后定义相应的功能
Stack.h#pragma once
// 支持动态增长的栈
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);注意:栈只能从后面入栈,从后面出栈.
#includeStack.h
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;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;ps-top;
}
bool STEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}
void StackPop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}
int STSize(Stack* ps)
{assert(ps);return ps-top;
}
最后我们来测试一下相关的功能
#includeStack.h
int main()
{Stack s;StackInit(s);StackPush(s, 1);StackPush(s, 2);StackPush(s, 3);int top StackTop(s);printf(%d , top);StackPop(s);StackPush(s, 4);StackPush(s, 5);while (!STEmpty(s)){int top StackTop(s);printf(%d , top);StackPop(s);}StackDestroy(s);return 0;
}
我们预期的结果是输入的倒着的,所以结果应该是 3 5 4 2 1
我们运行一下: 所以这就是一个栈. 这会我们介绍了栈,并完成了相关的操作,如果有什么不懂,或者错误,欢迎指出.
