栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
即:栈是仅限在表尾进行插入和删除的线性表。
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈是一个线性表,我们把允许插入和删除的一段称为栈顶。
和栈顶相对,另一端称为栈底,实际上,栈底的元素我们不需要关心。
栈的插入操作,叫做 入栈,也可称为 进栈、压栈。如下图所示,代表了三次入栈操作:
代码实现:
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
由于栈是由顺序表实现的,因此当空间不够需要扩容,入栈之后top需要+1为了记录下一个入栈位置。
栈的删除操作,叫做 出栈,也可称为 弹栈。如下图所示,代表了两次出栈操作:
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
--ps->top;
}
弹一次让top减一即可。
一直 出栈,直到栈为空,如下图所示:
即一直出栈到没有元素即可。
//想要直接清除栈也可以直接销毁,此代表着程序结束
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
对于一个栈来说只能获取 栈顶 数据,一般不支持获取 其它数据。
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
栈元素个数一般用一个额外变量存储,入栈 时加一,出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 **O ( 1 )**的时间复杂度获取栈元素个数。
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
当栈元素个数为零时,就是一个空栈,空栈不允许 出栈 操作。
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
对于顺序表,在 C语言 中表现为 数组,在进行 栈的定义 之前,我们需要考虑以下几个点: 1)栈数据的存储方式,以及栈数据的数据类型; 2)栈的大小; 3)栈顶指针;
此类信息都在对应的Stack.h头文件中定义
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);//栈的初始化
void StackDestory(ST* ps);//栈的销毁
void StackPush(ST* ps, STDataType x);//入栈
void StackPop(ST* ps);//出栈
STDataType StackTop(ST* ps);//获取栈顶元素
bool StackEmpty(ST* ps);//判断栈是否为空
int StackSize(ST* ps);//计算栈的数据个数
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void StackInit(ST* ps)
{
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
--ps->top;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPush(&st, 4);
StackPush(&st, 5);
printf("\n");
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
}
int main()
{
TestStack();
return 0;
}
栈的学习内容就到这里,下一章会是队列的实现以及oj题的讲解。