栈的介绍与实现
一. 概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价相对较小。
数组尾插时间复杂度：O(1) 链表尾插时间复杂度：O(N)
二.栈的实现
ps：由于栈的底层是数组，因此其结构实现与之前讲到的顺序表大致类似，在学习时可以进行类
比记忆。
stack.h
程序相关接口如下：
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
STDataType capacity;
STDataType top;
}ST;
//初始化和销毁
void STInit(ST*);
void STDestroy(ST*);
//栈顶---入数据,出数据
void StackPush(ST*, STDataType);
void StackPop(ST*);
//判空
bool StackEmpty(ST*);
//取栈顶元素
STDataType StackTop(ST*);
//获取栈中有效元素个数
int STSize(ST*);
test.c
程序相关测试代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STTest01()
{
ST st;
STInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
//StackPop(&st);
//StackPop(&st);
//StackPop(&st);
//StackPop(&st);
//StackPop(&st);
//
printf("size: %d\n", STSize(&st));
while (!StackEmpty(&st))
{
STDataType data = StackTop(&st);
printf("%d ", data);
StackPop(&st);
}
printf("\n");
printf("size: %d\n", STSize(&st));
}
int main()
{
STTest01();
return 0;
}
栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
分析：
1.首先对传入的指针进行断言检查
2.将数组置为空，容积和首元素位置置于0。
需注意：此处的top表示队头元素的下一个。
栈的销毁
void STDestroy(ST*ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
分析：
1.首先对传入的指针进行断言检查
2.释放指针并置为空，再将容积和队头元素位置置为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->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = 2 * newcapacity;
}
ps->arr[ps->top++] = x;
}
分析：
1.首先assert断言指针是否为空，并判断空间是否足够
2.如果需要增容，一般按2倍或者3倍扩容，避免频繁增容或者说增容过多导致的时间和空间销毁。
3.增容后，直接在栈顶处赋值即可。、
栈顶删除数据——出栈
与入栈之前需检查是否扩容原理类似，出栈之前需要检查栈是否为空。
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
分析：由于我们在之前已经提到，top表示栈顶数据位置的下一个，因此当栈为空时，top是否为0就是判断依据。
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
--ps->top;
}
分析：直接让top--即可，即使后续再有数据插入，也会直接覆盖原先已经删除的值。
输出栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top-1];
}
分析：top表示栈顶数据的下一个，因此直接返回top-1的数据即可。
注意：切勿把top-1写成top--，否则相当于不仅输出了栈顶数据，还进行了一次出栈。
输出栈的元素个数
int STSize(ST* ps)
{
return ps->top;
}
分析：top除了表示栈顶数据的下一个外，还可以直接表示元素个数，这与数组下标直接契合。
逐个输出栈中元素
while (!StackEmpty(&st))
{
STDataType data = StackTop(&st);
printf("%d ", data);
StackPop(&st);
}
printf("\n");
分析：取临时变量分别接收栈顶元素，输出后再删除栈顶元素，直至栈为空跳出循环即可。
三.完整代码
stack.c如下
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
void STDestroy(ST*ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = 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->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = 2 * newcapacity;
}
ps->arr[ps->top++] = x;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
--ps->top;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top-1];
}
int STSize(ST* ps)
{
return ps->top;
}