【数据结构与算法】第6课—数据结构之栈

1. 栈

• 栈：也是一种线性表，其数据结构与动态顺序表的数据结构类似
• 栈分为栈顶和栈底，在栈中，插入数据和删除数据被称为入栈和出栈
• 栈的相关操作都是在栈顶实现的，而栈底通常不会改变
• 栈的底层结构可以通过数组和链表实现，但是链表在入栈和出栈操作上，会出现指针指向改变的问题，相对而言，数组反而只需要改变其size(在栈中被称为栈顶top)大小即可，因此用数组来实现栈的底层更佳

---

---

2. 栈的初始化和栈的销毁

---

//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

3. 入栈和出栈（压栈）

---

//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);//空间满了--增容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//直接尾插ps->arr[ps->top] = x;ps->top++;
}//出栈
void StackPop(Stack* ps)
{assert(ps && ps->top);ps->top--;
}

4. 取栈顶元素并打印

---

//取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps && ps->arr);return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//打印
void StackPrint(Stack* ps)
{assert(ps);while (ps->top){//栈顶元素依次出栈STDataType top = StackTop(ps);printf("%d ", top);//每次出栈top--ps->top--;}
}

5. 栈的练习题

5.1 有效的括号

• 题目

---

• 思路

---

---

---

---

---

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//栈的数据结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}Stack;//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);//空间满了--增容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//直接尾插ps->arr[ps->top] = x;ps->top++;
}//出栈
void StackPop(Stack* ps)
{assert(ps && ps->top);ps->top--;
}//取栈顶元素
STDataType StackTop(Stack* ps)
{return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}bool isValid(char* s)
{Stack st;StackInit(&st);char* pi = s;//遍历字符串while (*pi != '\0'){//入栈if (*pi == '(' || *pi == '[' || *pi == '{')StackPush(&st, *pi);else{//取栈顶，判断char top = StackTop(&st);if ((top == '(' && *pi == ')') || (top == '[' && *pi == ']') || (top == '{' && *pi == '}'))StackPop(&st);else{StackDestroy(&st);return false;}}pi++;}//对比结束bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;
}