【栈】数据结构栈的实现
前言:
在之前的学习中,我们已经学习过了顺序表和链表的相关知识,今天我们将进入下一个知识点的学习,“栈”!!!
目录
- 1.栈的概念
- 2.栈的实现
- 3.栈的结构
- 4.接口实现
- 4.1栈的初始化
- 4.2销毁栈
- 4.3入栈操作
- 4.4出栈操作
- 4.5获取栈顶元素
- 4.6获取栈中有效元素个数
- 4.7检测栈是否为空,如果为空返回非零结果,如果不为空返回0
- 5.练习
1.栈的概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。不含元素的空表称为空栈。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
进出栈结构示意图如下:
我们通过具体的例子来进行仔细查看:
分析:开始时栈空间中有三个元素,当我们继续向栈空间中插入元素时,我们不难发现插入进去的元素在栈顶位置处,而当我们进行出栈操作时,通过上图不难发现后插入进去的元素反而先出栈,而最开始插入进去的元素则是最后才出栈了。
2.栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
3.栈的结构
在这里我们使用数组来定义栈,跟我们之前的顺序表和链表那样,我们还是需要定义一个容量来表示目前栈空间的大小capacity和栈空间中目前元素的个数,但是在这里我们实现的是栈所以这里命名 为top表示栈顶元素,具体如下:
typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int capacity;
int top; // 初始为0,表示栈顶位置下一个位置下标
}ST;
4.接口实现
我们主要实现的接口功能有以下的一些:
// 初始化栈
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);
4.1栈的初始化
代码如下:
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDatatype*)malloc(sizeof(STDatatype)*4);
if (ps->a == NULL)
{
perror("malloc fail");
exit(-1);
}
ps->top = 0;
ps->capacity = 4;
}
注意
4.2销毁栈
代码如下:
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
4.3入栈操作
代码如下:
void StackPush(ST* ps, STDatatype x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;
}
4.4出栈操作
代码如下:
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//特别注意
ps->top--;
}
4.5获取栈顶元素
代码如下:
STDatatype StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
注意
当我们进行获取栈顶元素的时候,要进行两个方面的断言,第一个就是对ps进行断言,不仅如此我们还需要对top进行相应的判断,如果其为0,则不能进行相应的操作!!!
4.6获取栈中有效元素个数
代码如下:
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
4.7检测栈是否为空,如果为空返回非零结果,如果不为空返回0
代码如下:
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
5.练习
1.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为 p1 , p2 , p3 ,…, pn ,若p1=n,则pi为()
A. i
B. n=i
C. n-i+1
D.不确定
解答
因为栈为先进后出的线性表,一个栈的入栈顺序为1,2,3,4,5,6…n,而输出序列的第一个元素为n,说明1,2,3.4,5,…n一次性全部进栈,在进行输出,所以p1=n,p2=n-1,…pi=n-i+1,所以选c
2.若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在()中情况。
A.5,4,3,2,1
B.2,1,5,4,3
C.4,3,1,2,5
D.2,3,5,4,1
解答
因为栈是先进后出的线性表。不难发现C选项中元素1比元素2先出栈,违背了栈的后进先出的规则,所以不可能出现C选项所示情况。