数据结构4——栈

1. 栈的概念及结构

栈的概念：

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

图解：

 

2. 栈的实现

1. 初始化栈

//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}

2. 销毁栈

//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

3. 入栈

//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}

4. 出栈

//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);//防止栈为空--ps->top;
}

5.获取栈顶元素

//获取栈顶元素
STDateType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}

6. 容量

//容量
int STSize(ST* ps)
{assert(ps);return ps->top;
}

7. 判空

//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

3. 测试

int main()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);//遍历栈，需要边获取边删除while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestroy(&st);return 0;
}

 

---

---

源代码 

Stack.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;void STInit(ST* ps);//初始化函数声明
void STDestroy(ST* ps);//销毁函数声明
void STPush(ST* ps, STDateType x);//入栈函数声明
void STPop(ST* ps);//出栈函数声明
STDateType STTop(ST* ps);//获取栈顶元素
int STSize(ST* ps);//容量
bool STEmpty(ST* ps);//判空

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);//防止栈为空--ps->top;
}//获取栈顶元素
STDateType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//容量
int STSize(ST* ps)
{assert(ps);return ps->top;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"int main()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);//遍历栈，需要边获取边删除while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestroy(&st);return 0;
}