【数据结构】【线性表】之栈(C语言)
回顾
顺序表和链表的区别和联系
顺序表:
优点:空间连续支持随机访问。
缺点:1.中间或前面的插入删除时间复杂度O(N)。
2.增容的代价比较大
链表(带头双向循环):
缺点:
以借点为单位存储,不支持随机访问。
优点:
1.任意位置插入删除时间复杂度为O(1)
2.没有增容消耗,按需申请结点空间,不用了直接释放。
栈
栈也是线性表,在逻辑上还是挨着放的。
栈的概念以及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶。
出栈:栈的删除操作叫做出栈。 出数据也在栈顶。
实现方式:
- 数组实现
总结:
相当于之前顺序表的尾插尾删,用尾做栈顶,非常合适,唯一缺陷就是,空间不够需要增容(影响不大)。
(顺序表——【线性表】之顺序表_半生瓜のblog-CSDN博客)
- 链表实现
出数据得找到前一个,这样的话用双向链表更好一些。
(所以说数据结构并没有规定用什么方法实现,只要能实现就行,对比的就是效率而已。)
也可以将单链表反过来。
总结:
如果用尾插做栈顶,用双向链表更好。
如果用单链表实现,就用头去做栈顶,这样入栈和出栈效率都是O(1)。
整体来说数组的效率更优一些。
结构定义
typedef int StackDataType;
typedef struct Stack
{
StackDataType* arry;
int top;//指向栈顶
int capacity;//栈的容量——能放几个数据
}Stack;
初始化
如果初识的top给0,意味着top指向栈顶的元素的下一个,top给-1,top指向栈顶元素。
一定不能为空的东西,可以使用断言来处理。OJ题不可以使用断言。
void StackInit(Stack* ps)
{
assert(ps);
ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4);
if (ps->arry == NULL)
{
printf("malloc fail");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
销毁
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->arry);
ps->arry = NULL;
ps->top = ps->capacity =0 ;
}
入栈
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
//满了
if (ps->top == ps->capacity)
{
StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType));
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
else
{
ps->arry = tmp;
ps->capacity *= 2;
}
}
ps->arry[ps->top] = x;
ps->top++;
}
出栈
void StackPop(Stack* ps)
{
assert(ps);
//如果栈空了调用top,直接终止程序报错
assert(ps->top > 0);
ps->top--;
}
返回栈顶元素
StackDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->arry[ps->top - 1];
}
返回栈中元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//真为空,假为非空。
}
小提示:
上面有的函数只有两行代码,如果直接用里面的那句代码,可以吗? 可以,但是不好,通过那句代码访问到,但严格来说你不应该去访问,这是一种耦合,耦合就是一种强关联, 调用函数,无需去想top在0还是在-1,只管用就完事了。(有点软件工程的思想)
调用
int main(void)
{
Stack ps;
StackInit(&ps);
StackPush(&ps,1);
StackPush(&ps,2);
StackPush(&ps,3);
while (!StackEmpty(&ps))
{
printf("%d ", StackTop(&ps));
//取完栈顶的数据,想取下一个,那就得删一下
StackPop(&ps);
}
printf("\n");
StackDestory(&ps);
return 0;
}