栈的概念及结构
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出
LIFO（Last In First Out）的原则。 - 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现
- 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
Stack.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; // 初始化栈 void StackInit(ST* ps); // 入栈 void StackPush(ST* ps, STDataType x); // 出栈 void StackPop(ST* ps); // 获取栈顶元素 STDataType StackTop(ST* ps); // 获取栈中有效元素个数 int StackSize(ST* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(ST* ps); // 销毁栈 void StackDestroy(ST* ps);
Stack.c
初始化栈
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
入栈
void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->capacity == ps->top) { STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("relloc fail!\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; }
出栈
void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
获取栈顶元素
STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; }
获取栈中有效元素个数
int StackSize(ST* ps) { assert(ps); return ps->top; }
检测栈是否为空
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
销毁栈
void StackDestroy(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; }
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" // 初始化栈 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; //top 表示指向栈顶元素 //ps->top = -1; //top 表示指向栈顶元素的下一个 ps->top = 0; } // 入栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->capacity == ps->top) { STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("relloc fail!\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } // 出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } // 获取栈顶元素 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } // 销毁栈 void StackDestroy(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; }
