栈

栈是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶，表头端称为栈低。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表

在这里插入图片描述

基本操作

栈的初始化
判断是否为空栈
判断是否为满栈
入栈
出栈

#include<stdio.h>
#include<malloc.h>#define STACK_INIT_SIZE 100  //栈的初始容量 
#define STACKINCREMENT 10    //容量增量
#define OK 1 
#define OVERFLOW -2
typedef int SDataType;
typedef int Status;typedef struct {SDataType* base; //栈底指针SDataType* top;  //栈顶指针int StackSize;   //当前已经分配的存储空间，以元素为单位 
}SqStack;//初始化顺序栈，构造一个空栈
Status InitStack(SqStack& S) {//分配存储空间 S.base = (SDataType*)malloc(STACK_INIT_SIZE * sizeof(SDataType));if (!S.base) {//如果分配失败，则返回error return OVERFLOW;}//S.top 始终指向栈顶元素的下一个位置 S.top = S.base;    //初始状态下为空栈 S.StackSize = STACK_INIT_SIZE;   //当前已经分配的存储容量为100个 return OK;
}//入栈
Status Push(SqStack& s, SDataType e) {SDataType* p;//首先判断栈是不是满的（上溢） if (s.top - s.base == s.StackSize) {//追加空间 p = (SDataType*)realloc(s.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SDataType));if (!p) {//如果没有找到符合条件的存储空间，则返回error return OVERFLOW;}//成功找到则使s.base指向p s.base = p;  //系统会将原来的内容复制过来s.top = s.base + s.StackSize;s.StackSize += STACKINCREMENT;}//先插入元素，然后使栈顶指针加 1 *(s.top) = e;s.top++;return OK;
}//出栈
Status Pop(SqStack& s, SDataType& e) {//判断是否会发生下溢 if (s.top != s.base) {s.top--;    //先将栈顶指针减 1 e = *(s.top);}else {return 0;}return e;
}//判断是否为空栈 
void judgeNull(SqStack& s) {if (s.top == s.base) {printf("此栈为空栈！\n");}else {printf("此栈不为空栈！\n");}
}//判断是否为满栈
void judgeFull(SqStack& s) {if (s.top - s.base == s.StackSize) {printf("栈满！\n");}else {printf("栈未满！\n");}
}int main() {SqStack s;SDataType element;InitStack(s);  //初始化栈//将1-5入栈for (int i = 1; i <= 10; i++) {Push(s, i);}judgeNull(s);judgeFull(s);printf("出栈：\n");//只要栈不为空 while (s.top != s.base) {Pop(s, element);    //出栈的元素用e接收 printf("%d ", element);}printf("\n");judgeNull(s);return 0;}