顺序栈
栈包含顺序栈和链栈，对应两种存储结构：顺序存储和链式存储，但它们同属于一个逻辑结构，即线性结构。
文章目录
顺序栈一、栈的定义名词解释栈的常用操作
二、栈的基本操作定义顺序栈创建顺序栈判空判满获取实际长度入栈操作（重点）出栈操作读栈顶遍历栈销毁栈
三、完整代码sqstack.csqstack.hmain.c
一、栈的定义
栈，从数据结构的方向来看，它属于线性表的一种，它的操作是线性表的操作的阉割，栈中存储的数据遵循：先进后出、后进先出的原则。
名词解释
栈顶：表示下一个要存储数据的地址。栈底：表示第一次存储数据的地址。空栈：表示没有存储数据的栈。入栈：也称压栈，就是将数据放入到栈顶的过程。出栈：就是将上一次存储的数据取出的过程。
栈的常用操作
SqStack *build_stack(void); //建立顺序栈
bool stack_is_empty(SqStack *S); //判空
bool stack_is_full(SqStack *S); //判满
int get_Length_Stack(SqStack *S); //获取栈的实际长度
bool stack_push(SqStack *S, Stack_t val); //入栈
Stack_t stack_pop(SqStack *S); //出栈
Stack_t stack_GetTop(SqStack *S); //读栈顶
void Print_Stack(SqStack *S); //遍历栈
bool Destroy_Stack(SqStack **S); //销毁栈
二、栈的基本操作
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素。本文只介绍顺序栈的操作。
定义顺序栈
#define Stack_Init_Size 10 // 初始化栈的最大长度
#define StackIncrement 10 // 若栈最大空间不够时，需要增加的长度
typedef int Stack_t;
typedef struct
{
Stack_t *base; // 栈底指针
Stack_t *top; // 栈顶指针
int stack_size; // 栈的最大长度
} SqStack;
创建顺序栈
建立时用malloc在堆区申请了两个空间，一个用于存储顺序栈的结构体，一个用于存放要压栈的数据，并对栈顶和栈底进行了初始化。
SqStack *build_stack(void) //建立顺序栈
{
SqStack *S = (SqStack *)malloc(sizeof(SqStack));
if (S == NULL)
return NULL;
S->base = (Stack_t *)malloc(Stack_Init_Size * sizeof(Stack_t));
if (S->base == NULL)
return NULL;
S->top = S->base;
S->stack_size = Stack_Init_Size;
return S;
}
判空判满
判断顺序栈是否为空，可以直接判断栈顶和栈底是否相等，相等即为空。
判断其是否未满，就判断栈顶和栈底偏移能存储的最大数量的Stack_t类型是否相等即可。
bool stack_is_empty(SqStack *S) //判空
{
return S->base == S->top;
}
bool stack_is_full(SqStack *S) //判满
{
return S->top == S->base + S->stack_size;
}
获取实际长度
用栈顶的指针变量减去栈底的指针变量就是中间存储的数量。
int get_Length_Stack(SqStack *S) //获取栈的实际长度
{
if (S == NULL)
return -1;
return S->top - S->base;
}
入栈操作（重点）
在入栈前需要判断当前栈是否装满，如果装满就要对其扩容，可以使用realloc函数重新开辟一个更大的空间，此时也需要改变栈顶的指向，因为有可能栈底已经被realloc函数换到了另一个位置，改变栈顶后，直接在栈顶放入要存放的数据就完成了入栈操作。
在这之前我们需要了解realloc函数，大致是这样的：
extern void *realloc(void *mem_address, unsigned int newsize);
如果p指向的空间之后有足够的空间可以追加，则直接追加，返回的是p原来的起始地址。如果p指向的空间之后没有足够的空间可以追加，则realloc函数会重新找一个新的内存区域，并且把原来内存空间的数据拷贝回来，释放旧的内存空间还给操作系统，最后返回新开辟的内存空间的起始地址。
bool stack_push(SqStack *S, Stack_t val) //入栈
{
if (S == NULL)
return false;
if (stack_is_full(S)) //栈的空间满时，重新开辟空间
{
S->base = (Stack_t *)realloc(S->base, (S->stack_size + StackIncrement) * sizeof(Stack_t));
if (S->base == NULL)
return false;
// 栈顶指针为栈底指针加上栈之前的最大长度
S->top = S->base + S->stack_size;
// 栈当前的最大长度等于栈之前的最大长度与增加的长度之和
S->stack_size += StackIncrement;
}
// *S->top++ = val;
*(S->top++) = val; // 先赋值，再将栈顶指针上移
return true;
}
出栈操作
因为栈遵循先进后出、后进先出的原则，因此出栈时只能放出最近一次入栈的数据，即放出栈顶的上一个地址的里面的数据，就完成出栈操作。
Stack_t stack_pop(SqStack *S) //出栈
{
if (S == NULL)
return false;
if (stack_is_empty(S))
return false;
return *(--S->top); //栈顶表示下一个数据要存放的地址、因此该地址中没有数据
}
读栈顶
Stack_t stack_GetTop(SqStack *S) //读栈顶
{
if (S == NULL)
return false;
if (stack_is_empty(S))
return false;
return *(S->top - 1); //获取栈顶元素的但是不出栈
}
遍历栈
通过get_length获取栈的实际长度，然后用循环从栈顶遍历到栈底，逐一打印栈中存放的值。
void Print_Stack(SqStack *S) //遍历栈
{
if (S == NULL)
return;
if (stack_is_empty(S))
{
puts("这个栈是空的！");
return;
}
for (int i = 1; i < get_Length_Stack(S) + 1; i++)
{
printf("%-4d", *(S->top - i));
}
puts("\n");
}
销毁栈
销毁时要先free实际数据地址，再free顺序栈结构体的地址。其次要在销毁之后将原顺序栈赋值未NULL，就要采用二级指针。
bool Destroy_Stack(SqStack **S) //销毁栈
{
if (*S == NULL)
return true;
free((*S)->base);
free(*S);
*S = NULL;
return true;
}
三、完整代码
sqstack.c
/*
* @Descripttion:
* @version:
* @Author: smile
* @Date: 2022-10-28 16:28:22
* @LastEditors: smile
* @LastEditTime: 2022-10-28 18:19:10
*/
#include "sqstack.h"
SqStack *build_stack(void) //建立顺序栈
{
SqStack *S = (SqStack *)malloc(sizeof(SqStack));
if (S == NULL)
return NULL;
S->base = (Stack_t *)malloc(Stack_Init_Size * sizeof(Stack_t));
if (S->base == NULL)
return NULL;
S->top = S->base;
S->stack_size = Stack_Init_Size;
return S;
}
bool stack_is_empty(SqStack *S) //判空
{
return S->base == S->top;
}
bool stack_is_full(SqStack *S) //判满
{
return S->top == S->base + S->stack_size;
}
int get_Length_Stack(SqStack *S) //获取栈的实际长度
{
if (S == NULL)
return -1;
return S->top - S->base;
}
bool stack_push(SqStack *S, Stack_t val) //入栈
{
if (S == NULL)
return false;
if (stack_is_full(S)) //栈的空间满时，重新开辟空间
{
S->base = (Stack_t *)realloc(S->base, (S->stack_size + StackIncrement) * sizeof(Stack_t));
if (S->base == NULL)
return false;
// 栈顶指针为栈底指针加上栈之前的最大长度
S->top = S->base + S->stack_size;
// 栈当前的最大长度等于栈之前的最大长度与增加的长度之和
S->stack_size += StackIncrement;
}
// *S->top++ = val;
*(S->top++) = val; // 先赋值，再将栈顶指针上移
return true;
}
Stack_t stack_pop(SqStack *S) //出栈
{
if (S == NULL)
return false;
if (stack_is_empty(S))
return false;
return *(--S->top); //栈顶表示下一个数据要存放的地址、因此该地址中没有数据
}
Stack_t stack_GetTop(SqStack *S) //读栈顶
{
if (S == NULL)
return false;
if (stack_is_empty(S))
return false;
return *(S->top - 1); //获取栈顶元素的但是不出栈
}
void Print_Stack(SqStack *S) //遍历栈
{
if (S == NULL)
return;
if (stack_is_empty(S))
{
puts("这个栈是空的！");
return;
}
for (int i = 1; i < get_Length_Stack(S) + 1; i++)
{
printf("%-4d", *(S->top - i));
}
puts("\n");
}
bool Destroy_Stack(SqStack **S) //销毁栈
{
if (*S == NULL)
return true;
free((*S)->base);
free(*S);
*S = NULL;
return true;
}
void run_stack(void) //运行顺序栈实例
{
SqStack *S = build_stack();
if (S == NULL)
perror("建立失败\n");
else
puts("建立成功！");
puts("\n-------------入栈9个:");
for (int i = 1; i < 10; i++)
stack_push(S, i);
printf("此时栈的个数：%d,当前栈的最大长度是:%d\n", get_Length_Stack(S), S->stack_size);
Print_Stack(S);
puts("\n-------------再入栈9个:");
for (int i = 1; i < 10; i++)
stack_push(S, i * 100);
printf("此时栈的个数：%d,当前栈的最大长度是:%d\n", get_Length_Stack(S), S->stack_size);
Print_Stack(S);
puts("\n-------------出栈18个:");
for (int i = 1; i < 19; i++)
printf("第%-2d次出了%-4d\n", i, stack_pop(S));
printf("此时栈的个数：%d,当前栈的最大长度是:%d\n", get_Length_Stack(S), S->stack_size);
int rand_t = rand() % 150 + 1;
printf("\n-------------随机入栈%d个:\n", rand_t);
for (int i = 0; i < rand_t; i++)
stack_push(S, rand() % 1000);
printf("此时栈的个数：%d,当前栈的最大长度是:%d\n", get_Length_Stack(S), S->stack_size);
printf("此时栈顶是：%d\n", stack_GetTop(S));
Print_Stack(S);
puts("\n-------------销毁栈:");
Destroy_Stack(&S) == 1 ? puts("销毁成功！") : puts("销毁失败！");
}
sqstack.h
/*
* @Descripttion:
* @version:
* @Author: smile
* @Date: 2022-10-28 16:28:30
* @LastEditors: smile
* @LastEditTime: 2022-10-28 21:08:34
*/
#ifndef _SQSTACK_H_
#define _SQSTACK_H_
#include
#include
#include
#include
#include
#include
#include
#define Stack_Init_Size 10 // 初始化栈的最大长度
#define StackIncrement 10 // 若栈最大空间不够时，需要增加的长度
//不定长型
typedef int Stack_t;
typedef struct
{
Stack_t *base; // 栈底指针
Stack_t *top; // 栈顶指针
int stack_size; // 栈的最大长度
} SqStack;
SqStack *build_stack(void); //建立顺序栈
bool stack_is_empty(SqStack *S); //判空
bool stack_is_full(SqStack *S); //判满
int get_Length_Stack(SqStack *S); //获取栈的实际长度
bool stack_push(SqStack *S, Stack_t val); //入栈
Stack_t stack_pop(SqStack *S); //出栈
Stack_t stack_GetTop(SqStack *S); //读栈顶
void Print_Stack(SqStack *S); //遍历栈
bool Destroy_Stack(SqStack **S); //销毁栈
void run_stack(void); //运行顺序栈实例
#endif
main.c
#include "sqstack.h"
int main(void)
{
srand((int)time(NULL));
run_stack(); //运行顺序栈实例
system("pause");
return 0;
}