数据结构栈和队列
1.栈
1.1概念和结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
用什么来定义栈呢
1.数组，可定义一个数组，最后面定义为栈顶，在最后面进行数据的加入和删除（定义一个数组有效数据为size,在size下标进行就好了）
2.单链表，在末尾进行的话，找到尾结点很难，如果为n个数据，那么时间复杂度就为o(n),所以在头结点定义为栈顶，一样可以实现栈
3.双向链表，无论是头结点还是尾结点定义为栈顶，进行插入和删除的时间复杂度都为o(1)
但双向链表比单链表要申请更多空间，排除
但是我更推荐数组，因为数组是一片连续的空间
1.2栈的代码实现
1.2.1栈的结构
//定义栈的结构
typedef int STDataType;
typedef struct stack
{
//int* arr; //不止可以定义整形
STDataType* arr;
int capacity; //栈的空间大小
int top; //栈顶,相当于顺序表的size，表示数据的有效个数，在当前输入输出数据
}ST1.2.2 栈的初始化和删除
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;
}1.2.3入栈和出栈
void StackPush(ST* ps, STDataType x)//x表示的是要插入的数据
{
assert(ps);
//判断空间是否足够
if (ps->capacity == ps->top)
{
//因为一开始的ps->capacity是为0的，如果直接乘2相当于没有乘
int newCppacity = ps->capacity == 0 ? 4: 2 * ps->capacity;
//改变栈的空间大小
STDataType* tmp = (STDataType*)realloc(ps->arr, newCppacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCppacity;
}
//此时空间是必够的。
ps->arr[ps->top++] = x;//ps->top++先使用再++
}
void StackPop(ST* ps)//出数据
{
assert(ps);
//如果栈为空，不能出数据
assert(!StackEmpty(ps));
--ps->top;
}
bool StackEmpty(ST* ps)//判空
{
assert(ps);
return ps->top == 0;
//如果ps->top为0，返回true，为空。
}1.2.4取栈顶元素
//取栈顶元素
STDataType StakeTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//没有元素，出不了
return ps->arr[ps->top - 1];
}栈里的数据不能被遍历，也不能被随机访问，只能取栈顶元素
1.2.5获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}1.3栈的算法题
有效的括号
20. 有效的括号 - 力扣（LeetCode）
思路：把左括号，左小括号，左大括号放入栈中，不是的话和栈顶元素比较是否匹配。
typedef char STDataType;
typedef struct stack
{
//int* arr; //不止可以定义整形
STDataType* arr;
int capacity; //栈的空间大小
int top; //栈顶,相当于顺序表的size，表示数据的有效个数，在当前输入输出数据
}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)//x表示的是要插入的数据
{
assert(ps);
//判断空间是否足够
if (ps->capacity == ps->top)
{
//因为一开始的ps->capacity是为0的，如果直接乘2相当于没有乘
int newCppacity = ps->capacity == 0 ? 4: 2 * ps->capacity;
//改变栈的空间大小
STDataType* tmp = (STDataType*)realloc(ps->arr, newCppacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCppacity;
}
//此时空间是必够的。
ps->arr[ps->top++] = x;//ps->top++先使用再++
}
void StackPop(ST* ps)//出数据
{
assert(ps);
//如果栈为空，不能出数据
assert(!StackEmpty(ps));
--ps->top;
}
bool StackEmpty(ST* ps)//判空
{
assert(ps);
return ps->top == 0;
//如果ps->top为0，返回true，为空。
}
//取栈顶元素
STDataType StakeTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//没有元素，出不了
return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
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))
{
return false;
}
char ch=StackPop(&st);
if((*ps==')'&&ch=='(')
||(*ps==']'&&ch=='[')
||(*ps=='}'&&ch=='{'))
{
StackPop(&st);
}
else
{
//销毁
STDestroy(&st);
//不匹配
return false;
}
}
ps++;
}
//可能示例里只要一个左括号，那么要判断栈是否为空
bool ret=StackEmpty(&st)==true;
//如果为空，则ret==true，不为空，ret=false
//销毁
STDestroy(&st);
return ret;
}2.队列
2.1概念
概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头
队列也不能遍历
队列底层用什么来写合适呢
数组：把后面当队尾插入数据，时间复杂度为o(1)，但是前面当队头删除数据，此时整体向前挪一位，时间复杂度为o(n).
单链表：把后面当队尾插入数据，要遍历找到尾结点，时间复杂度为o(n)，前面当队头删除数据，只要记住头结点的下一个位置，再把头结点删除就可以了，时间复杂度为o（1）
两个不分伯仲，我们要优化一下，数组我想不到，只能用单链表的来写，只需要额外定义一个指针，这个指针指向尾结点，这样单链表时间复杂度都为o（1）.
2.2队列的结构
队列用单链表来写，所以单链表需要定义，队列也需要定义
//定义队列的结构
typedef int QDateType;
typedef struct QueueNode//队列结点的结构
{
//int date;
QDateType date;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;//头结点
QueueNode* ptail;//尾结点
}Queue;
2.3初始化与销毁
2.3.1初始化
void QueueInit(Queue* pq)//初始化
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
2.3.2销毁
定义一个pcur，循环的free掉
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//队列不为空
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}2.4入队列和出队列
2.4.1入队列
直接往尾结点的下一个位置添加，然后改变尾结点的指针
队列为空的话，即为头结点也为 尾结点。
// ⼊队列，队尾
void QueuePush(Queue* pq, QDateType x)
{
assert(pq);
//申请新节点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->date = x;
newnode->next = NULL;
//判断链表为不为空，让ptail 和newnode产生联系
if (pq->phead == NULL)
{//队列为空
pq->phead = pq->ptail == newnode;
}
else
{//不为空
pq->ptail->next = newnode;
pq->ptail = newnode;
}
}2.4.2判空
/队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
//都为null则返回true
}2.4.3出队列
把头结点删掉，在改变头结点的位置
队列为空的话则不能出队列
// 出队列，队头
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//不为null
// 只有一个结点的情况
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//删除对头元素
QueueNode* next = pq->phead->next;
ferr(pq->phead);
pq->phead = next;
}
}2.5取队头，队尾数据
//取对头数据
QDateType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->date;
}
//取队尾数据
QDateType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->date;
}2.6队列有效元素个数
方案1：
强行遍历，但是队列是不能遍历的
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* pcur = pq->phead;
while (pcur)
{
size++;
pcur = pcur->next;
}
return size;
}效率很低，时间复杂度为o（n）
方案2：
直接在队列的结构中添加个size，在入队列是size++，出队列时size--；
typedef int QDateType;
typedef struct QueueNode//队列结点的结构
{
//int date;
QDateType date;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;//头结点
QueueNode* ptail;//尾结点
int size;//保存队列有效数据个数
}Queue;//队列有效元素个数
int QueueSize(Queue* pq)
{
return pq->size;
}