目录
- 1.栈的概念及结构
- 2.栈的实现
- 3.栈的代码实现
- 4.相关例题
•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!
1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
讲到栈，就要提到它的两种基本操作：压栈（入栈）和出栈。
入栈和出栈遵循一种规则：后进先出（进入栈晚的数据先出栈，就像是先进去的数据被后进入的数据压住了，只能先把上面的数据拿走才能拿到下面的数据）。
连续入栈和连续出栈：
2.栈的实现
对于栈的实现，我们有两种结构可以选择：顺序表和链表。考虑到先进后出的规则，链表尾插和尾删的成本比顺序表高，不太适合，顺序表尾插和尾删只需要改变加减的size的大小就可以做到，所以我们采用顺序表来实现栈。
关于栈，我们要实现以下几个接口：
3.栈的代码实现
test.c
#include "Stack.h"
void menu()
{
printf("********************************************\n");
printf("*************** 请选择 ***************\n");
printf("****** 1.PushStack 2.PopStack *******\n");
printf("****** 3.PrintStack 4.TopStack *******\n");
printf("****** 5.SizeStack 6.CheckEmpty *******\n");
printf("****** 0.Exit *******\n");
printf("********************************************\n");
}
int main()
{
int input = 0;
int value = 0;
Stack s;
Init_Stack(&s);
do
{
menu();
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入你要入栈的值>:");
scanf("%d", &value);
Push_Stack(&s, value);
break;
case 2:
Pop_Stack(&s);
break;
case 3:
Print_Stack(&s);
break;
case 4:
if (Empty_Stack(&s) != 0)
{
printf("栈为空\n");
break;
}
printf("栈顶的元素是%d\n", Top_Stack(&s));
break;
case 5:
printf("栈中有效元素的个数为%d\n", Size_Stack(&s));
break;
case 6:
if (Empty_Stack(&s) != 0)
printf("栈为空\n");
else
printf("栈不为空\n");
break;
case 0:
Destroy_Stack(&s);
printf("销毁栈成功\n");
break;
default:
printf("选择错误，请重新选择\n");
break;
}
} while (input);
return 0;
}
Stack.c
#include "Stack.h"
//初始化栈
void Init_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
STDataType* tmp = (STDataType*)malloc(3*sizeof(STDataType));
if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序
{
perror("Init_Stack\n");
exit(1);
}
ptr->stack = tmp; //申请空间成功就正常初始化
ptr->capacity = 3;
ptr->size = 0;
}
//销毁栈
void Destroy_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
free(ptr->stack);
ptr->stack = NULL;
}
//检查栈是否满了，满了则扩容
void Check_Capacity(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
if (ptr->size == ptr->capacity)
{
STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));
if (tmp == NULL) //申请空间可能失败，失败会返回NULL，不能解引用，要终止程序
{
perror("Check_Capacity\n");
exit(1);
}
ptr->stack = tmp; //要把申请到的空间赋给原指针，不然后面操作不了这块空间
ptr->capacity *= 2; //扩容之后要修改capacity的值，不然检查栈的大小时会一直扩容
}
}
//打印栈里面的数据
void Print_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
for (int i = 0; i < ptr->size; i++)
{
printf("%d ", ptr->stack[i]);
}
printf("\n");
}
//数据入栈
void Push_Stack(Stack* ptr,STDataType val)
{
assert(ptr); // ptr要解引用，不能为空指针
Check_Capacity(ptr); //入栈时要检查空间是否足够
ptr->stack[ptr->size] = val;
ptr->size++;
}
//数据出栈
void Pop_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
if (ptr->size == 0)
{
printf("栈为空\n");
return;
}
ptr->size--; //出栈就相当于顺序表可以读取的元素少一个，size - 1 就可以了
}
//获取栈顶数据
STDataType Top_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
return ptr->stack[ptr->size-1];
}
//获取栈储存的元素个数
int Size_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
return ptr->size;
}
//判断栈是否为空
int Empty_Stack(Stack* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
if (ptr->size == 0)
return 1;
else
return 0;
}
Stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>
typedef int STDataType; // 栈储存的数据的类型
typedef struct Stack
{
STDataType* stack; //动态开辟的空间，在堆上
int size; //储存元素的个数
int capacity; //栈的大小（容量），可变化
}Stack;
//栈的初始化
void Init_Stack(Stack* ptr);
//打印栈里面的数据
void Print_Stack(Stack* ptr);
//数据入栈
void Push_Stack(Stack* ptr, STDataType val);
//数据出栈
void Pop_Stack(Stack* ptr);
//获取栈顶数据
STDataType Top_Stack(Stack* ptr);
//获取栈储存元素的个数
int Size_Stack(Stack* ptr);
//判断栈是否为空
int Empty_Stack(Stack* ptr);
//销毁栈
void Destroy_Stack(Stack* ptr);
4.相关例题
题目描述：
参考解析：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* stack;
int size;
int capacity;
}Stack;
void Init_Stack(Stack* ptr)
{
assert(ptr);
STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));
if (tmp == NULL)
{
perror("Init_Stack\n");
exit(1);
}
ptr->stack = tmp;
ptr->capacity = 3;
ptr->size = 0;
}
void Destroy_Stack(Stack* ptr)
{
assert(ptr);
free(ptr->stack);
ptr->stack = NULL;
}
void Check_Capacity(Stack* ptr)
{
assert(ptr);
if (ptr->size == ptr->capacity)
{
STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("Check_Capacity\n");
exit(1);
}
ptr->stack = tmp;
ptr->capacity *= 2;
}
}
void Print_Stack(Stack* ptr)
{
assert(ptr);
for (int i = 0; i < ptr->size; i++)
{
printf("%d ", ptr->stack[i]);
}
printf("\n");
}
void Push_Stack(Stack* ptr, STDataType val)
{
assert(ptr);
Check_Capacity(ptr);
ptr->stack[ptr->size] = val;
ptr->size++;
}
void Pop_Stack(Stack* ptr)
{
assert(ptr);
if (ptr->size == 0)
{
return;
}
ptr->size--;
}
STDataType Top_Stack(Stack* ptr)
{
assert(ptr);
return ptr->stack[ptr->size - 1];
}
int Size_Stack(Stack* ptr)
{
assert(ptr);
return ptr->size;
}
int Empty_Stack(Stack* ptr)
{
assert(ptr);
if (ptr->size == 0)
return 1;
else
return 0;
}
//解题思路：
//该题比较简单，是对栈特性很好的应用，具体操作如下：
//循环遍历String中的字符，逐个取到每个括号，如果该括号是：
//1. 左括号，直接入栈
//2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false
//否则继续循环
//循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配
bool isValid(char* s)
{
Stack st;
Init_Stack(&st);
while (*s)
{
switch (*s)
{
//是左括号则入栈
case '(':
case '{':
case '[':
Push_Stack(&st, *s);
break;
//是右括号则从栈顶获取左括号来检测是否匹配
case ')':
case '}':
case ']':
if (Size_Stack(&st) == 0) // 如果有右括号，而栈里面左括号已经没有了，就不是匹配的
return false;
char tmp = Top_Stack(&st);
Pop_Stack(&st); // 取完元素要从栈中删除
if (tmp == '(' && *s != ')')
return false;
else if (tmp == '{' && *s != '}')
return false;
else if (tmp == '[' && *s != ']')
return false;
}
s++;
}
if (Empty_Stack(&st)) // 如果完全匹配，循环结束时栈内一定是空的
return true;
else
return false;
}
![数据结构 - 队列 [动画+代码注释超详解]，萌新轻松上手！！！](https://img-blog.csdnimg.cn/direct/ab29b97fc1ff43ccad891a86e54392ad.gif)
