【数据结构初阶】深度理解 “栈” （附源码）

hello，又见面了！

1. 栈的概念与结构

2、栈的实现

Stack.h

Stack.c

test.c

3、习题

正文开始——

1. 栈的概念与结构

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

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

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

【图解】

栈的底层结构

内存比较：双向链表比单链表多了一种指针，内存占用就相对多一些；数组和单链表，数组每次都以2倍大小增容，正因如此，无需多次增容，而单链表每次增加数据都要申请空间，删除数据要释放空间，较为繁琐。

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更好一些，因为数组在尾插数据时代价更小。

2、栈的实现

栈里的数据不能被遍历，不能被随机访问。每次取数据只能取栈顶数据

Stack.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;  //栈的容量int top;       //栈顶
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestroy(ST* ps);//入数据
void StackPush(ST* ps, STDataType x);//出数据
void StackPop(ST* st);//取栈顶元素
STDataType StackTop(ST* ps);//判空
bool StackEmpty(ST* ps);//获取栈中有效的数据个数
int STsize(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;  //此时栈为空，栈顶=栈底
}//销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//入数据
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->capacity == ps->top){//申请空间int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc file!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//出数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效的数据个数
int STsize(ST* ps)
{assert(ps);return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"void STTest()
{ST st;STInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);StackPush(&st,4);StackPush(&st,5);printf("size:%d\n", STsize(&st));/*StackPop(&st);*///循环出栈，直到栈为空while (!StackEmpty(&st)){STDataType data = StackTop(&st);printf("%d ", data);//出栈StackPop(&st);}printf("size:%d\n", STsize(&st));STDestroy(&st);
}int main()
{STTest();return 0;
}

3、习题

【思路】


//定义栈的结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int capacity;  //栈的容量int top;       //栈顶
}ST;//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;  //此时栈为空，栈顶=栈底
}//销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//入数据
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->capacity == ps->top){//申请空间int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc file!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}bool isValid(char* s) {ST st;STInit(&st);char* ps=s;while(*ps!='\0'){//左括号，入栈if(*ps=='('||*ps=='['||*ps=='{'){StackPush(&st,*ps);}else  //右括号，与栈顶元素判断是否匹配，匹配，出栈，不匹配，返回false{if(StackEmpty(&st)){STDestroy(&st);return false;}char ch=StackTop(&st);if(*ps==')'&&ch=='('||*ps=='}'&&ch=='{'||*ps==']'&&ch=='['){StackPop(&st);}else{STDestroy(&st);return false;}}ps++;}bool ret=StackEmpty(&st)==true;STDestroy(&st);return ret;
}

至此，栈，结束——

完——