C语言数据结构——详细讲解《栈》
前言一、栈的概念二、栈的定义三、栈的操作1.初始化栈2. 入栈操作3. 出栈操作4. 获取栈顶元素5. 检查栈是否为空6.释放栈内存
四、栈的例题五、本文的所有代码Stack.cStack,h最后一题代码
前言
在 C 语言编程中，数据结构是非常重要的一部分，它能够帮助我们更高效地组织和处理数据。今天，我们就来详细讲解一下其中的栈数据结构。
一、栈的概念
“栈” 在计算机中是一种数据结构，是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出的原则
压栈（进栈、入栈）：栈的插入操作叫做进栈（压栈、入栈），入数据在栈顶出栈：栈的删除操作叫做出栈，出数据也在栈顶
二、栈的定义
栈的结构通常由一个数组或链表来实现。在数组实现中，栈顶通常由一个变量来指向，这个变量记录了栈顶元素的索引。每次入栈操作会增加这个索引，每次出栈操作会减小这个索引。在链表实现中，栈顶是链表的头节点，入栈操作相当于在链表头部插入一个新节点，出栈操作相当于删除链表的头节点。
下面我们来详细讲一下栈的链式结构
首先，我们要定义栈的数据结构
typedef struct Stack
{
int* arr;
int top;
int capacity;
} Stack;
arr指栈中的元素top指栈顶capacity表示栈的容量
三、栈的操作
1.初始化栈
有了栈的结构体定义，我们需要对栈进行初始化
void initStack(Stack* ps)
{
ps->capacity = 4;
ps->top = 0;
ps->arr = (int*)malloc(ps->capacity * sizeof(int));
assert(ps->arr!= NULL);
}
首先，把栈的初始容量设置为 4然后，将栈顶top设置为 0，表示此时栈是空的接着，使用malloc函数来动态分配内存，以便能够存储栈的元素
2. 入栈操作
栈初始化好了之后，接下来就往栈里放元素
void push(Stack* ps, int x) {
if (ps->top == ps->capacity)
{
// 栈满，扩容
int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
if (tmp == NULL) {
perror("realloc fail\n");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
这个函数就是用来把一个元素x压入栈中的
首先，检查一下栈是否已满了 ps->top == ps->capacity如果栈满了，就得进行扩容操作
int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
如果当前栈的容量是 0 ，就把新容量设为 4；要是当前容量不为 0，就是当前容量的两倍
int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
然后使用realloc函数来重新分配内存
最后，把元素x放到arr[top]这个位置上，然后再把top加 1，这样就表示栈顶元素的位置更新
3. 出栈操作
int pop(Stack* ps)
{
assert(ps->top > 0);
return ps->arr[--ps->top];
}
把top减 1，再返回arr[top]的值，这个值就是栈顶元素
4. 获取栈顶元素
int top(Stack* ps)
{
assert(ps->top > 0);
return ps->arr[ps->top - 1];
}
如果栈不为空，那就返回arr[top - 1]的值，这个值就是栈顶元素的值
5. 检查栈是否为空
int isEmpty(Stack* ps)
{
return ps->top == 0;
}
如果top等于 0，那就说明栈是空的，这时候函数就会返回 1；要是top不等于 0，那就说明栈里还有元素，函数就会返回 0
6.释放栈内存
void freeStack(Stack* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
以上便是栈的全部操作，下面给大家带来一道栈的例题，应用一下所学的知识
四、栈的例题
链接地址》》》》》》有效括号
大家先思考一下怎么做 题目讲解思路，将左括号看为入栈，右括号看为出栈
#include
#include
#include
// 定义栈的数据结构
typedef struct Stack {
int* arr;
int top;
int capacity;
} Stack;
// 初始化栈
void initStack(Stack* ps) {
ps->capacity = 4;
ps->top = 0;
ps->arr = (int*)malloc(ps->capacity * sizeof(int));
assert(ps->arr!= NULL);
}
// 入栈操作
void push(Stack* ps, int x) {
if (ps->top == ps->capacity) {
// 栈满，扩容
int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
if (tmp == NULL) {
perror("realloc fail\n");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
// 出栈操作
int pop(Stack* ps) {
assert(ps->top > 0);
return ps->arr[--ps->top];
}
// 获取栈顶元素
int top(Stack* ps) {
assert(ps->top > 0);
return ps->arr[ps->top - 1];
}
// 检查栈是否为空
int isEmpty(Stack* ps) {
return ps->top == 0;
}
// 释放栈内存
void freeStack(Stack* ps) {
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
bool isValid(char* s) {
Stack st;
initStack(&st);
char* pi = s;
while (*pi!= '\0') {
if (*pi == '(' || *pi == '{' || *pi == '[') {
// 入栈
push(&st, *pi);
} else {
// 判断，取栈
if (isEmpty(&st)) {
freeStack(&st);
return false;
}
char top = (char)pop(&st);
if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
freeStack(&st);
return false;
}
}
pi++;
}
bool ret = isEmpty(&st);
freeStack(&st);
return ret;
}
下面详细讲解一下，对比上面代码增加的部分
bool isValid(char* s) {
Stack st;//定义了一个名为st的Stack类型的变量,用于辅助判断括号的有效性
initStack(&st);//调用initStack函数对栈st进行初始化
char* pi = s;
while (*pi!= '\0') {
if (*pi == '(' || *pi == '{' || *pi == '[') {
// 入栈
push(&st, *pi);
} else {
// 判断，取栈
if (isEmpty(&st)) {
freeStack(&st);
return false;
}
char top = (char)pop(&st);
if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
freeStack(&st);
return false;
}
}
pi++;
}
bool ret = isEmpty(&st);
freeStack(&st);
return ret;
}
首先定义了一个字符指针pi，并将其初始化为指向传入的字符串s的首地址。这个指针将用于遍历字符串s。接着循环遍历栈中的元素如果等于左括号则入栈然后调用push函数将该左括号字符压入栈st中如果pi所指向的字符不是左括号首先检查栈st是否为空。如果栈不为空，调用pop函数从栈st中弹出栈顶元素，并将其转换为char类型后赋值给变量top如果不匹配，则调用freeStack函数释放栈的内存
bool ret = isEmpty(&st); 当遍历完整个字符串s后，检查栈st是否为空。如果栈为空，说明所有的左括号都找到了对应的右括号，将true赋值给ret；否则，将false赋值给ret
最后返回ret的值
五、本文的所有代码
Stack.c
#include "Stack.h"
int main() {
Stack myStack;
initStack(&myStack);
// 入栈几个数据实例
push(&myStack, 10);
push(&myStack, 20);
push(&myStack, 30);
// 获取栈顶元素并打印
printf("当前栈顶元素: %d\n", top(&myStack));
// 出栈操作并打印出栈元素
printf("出栈元素: %d\n", pop(&myStack));
// 再次获取栈顶元素并打印
printf("当前栈顶元素: %d\n", top(&myStack));
// 检查栈是否为空并打印结果
if (isEmpty(&myStack)) {
printf("栈为空\n");
}
else {
printf("栈不为空\n");
}
// 释放栈内存
freeStack(&myStack);
return 0;
}
Stack,h
#pragma once
#include
#include
#include
// 定义栈的数据结构
typedef struct Stack {
int* arr;
int top;
int capacity;
} Stack;
// 初始化栈
void initStack(Stack* ps) {
ps->capacity = 4;
ps->top = 0;
ps->arr = (int*)malloc(ps->capacity * sizeof(int));
assert(ps->arr != NULL);
}
// 入栈操作
void push(Stack* ps, int x) {
if (ps->top == ps->capacity) {
// 栈满，扩容
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
if (tmp == NULL) {
perror("realloc fail\n");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
// 出栈操作
int pop(Stack* ps) {
assert(ps->top > 0);
return ps->arr[--ps->top];
}
// 获取栈顶元素
int top(Stack* ps) {
assert(ps->top > 0);
return ps->arr[ps->top - 1];
}
// 检查栈是否为空
int isEmpty(Stack* ps) {
return ps->top == 0;
}
// 释放栈内存
void freeStack(Stack* ps) {
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
最后一题代码
#include
#include
#include
// 定义栈的数据结构
typedef struct Stack {
int* arr;
int top;
int capacity;
} Stack;
// 初始化栈
void initStack(Stack* ps) {
ps->capacity = 4;
ps->top = 0;
ps->arr = (int*)malloc(ps->capacity * sizeof(int));
assert(ps->arr!= NULL);
}
// 入栈操作
void push(Stack* ps, int x) {
if (ps->top == ps->capacity) {
// 栈满，扩容
int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity;
int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
if (tmp == NULL) {
perror("realloc fail\n");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
// 出栈操作
int pop(Stack* ps) {
assert(ps->top > 0);
return ps->arr[--ps->top];
}
// 获取栈顶元素
int top(Stack* ps) {
assert(ps->top > 0);
return ps->arr[ps->top - 1];
}
// 检查栈是否为空
int isEmpty(Stack* ps) {
return ps->top == 0;
}
// 释放栈内存
void freeStack(Stack* ps) {
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
bool isValid(char* s) {
Stack st;
initStack(&st);
char* pi = s;
while (*pi!= '\0') {
if (*pi == '(' || *pi == '{' || *pi == '[') {
// 入栈
push(&st, *pi);
} else {
// 判断，取栈
if (isEmpty(&st)) {
freeStack(&st);
return false;
}
char top = (char)pop(&st);
if ((top == '(' && *pi!= ')') || (top == '[' && *pi!= ']') || (top == '{' && *pi!= '}')) {
freeStack(&st);
return false;
}
}
pi++;
}
bool ret = isEmpty(&st);
freeStack(&st);
return ret;
}
非常感谢您的阅读，喜欢的话记得三连哦