连连跨境电商网站开发_网站维护员工作内容_网站底部友情链接_品牌推广活动有哪些

---

前言

• 在 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 <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈的数据结构
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 <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈的数据结构
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 <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈的数据结构
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;
}

非常感谢您的阅读，喜欢的话记得三连哦