大家好!这篇我们继续讲解数据结构里的栈。
栈的概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
我们知道了栈的概念,现在就开始去实现它。
栈的实现
栈一般分为数组栈和链式栈:
相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的结构
首先,我们来看一下栈的结构:
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;//记录栈顶
int capacity;
}ST;
和顺序表类似。
栈的初始化
这里的top也可以赋值-1,但意义不同。
top为0时,当数据放进去时,top++。
top为-1时,当top++后,数据才放进去时。
栈的销毁
栈的销毁也简单,直接看代码:
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
这里,我们先写栈是否为空这个函数,后面会用到。
我们直接用一个判断来返回就行了。
删除函数
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
这里我们用断言来判断栈是否为空,而不是用if(ps->top>0)来判断,这是为什么呢?
这和我们初始化有关:在上面初始化我们说到,初始化有两种方式。
1.top=0
2.top=-1
如果我们选择if语句,就不好了,因为如果创作者写初始化时用的是top=-1,那么使用者还要知道它里面的实现是什么样的。
但我们使用函数,就在StackEmpty函数里改,这样是比较规范的。
取栈顶的数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
这里,我们还是使用StackEmpty函数,这样会比较规范。
这里的top指向的是栈顶元素下一个位置,所以我们取栈顶元素要-1。
栈里数据的个数
这里也是非常的简单,这里的top我们初始化的是0,它和顺序表里的size是相似的,所以top就是栈里数据的个数。
代码如下:
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
插入函数
它和顺序表的也是类似的,我们直接看代码:
到这里,栈的实现就结束了,只要你会顺序表,栈的实现就会非常简单,如果大家觉得有帮助,希望大家能够支持一下,谢谢大家!