1、栈
1.1 概念与结构
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈里面的数据元素遵循后进先出的原则。栈的底层实现一般可以使用数组或者链表来实现，但数组的实现更优，因为空间消耗更少。
1.2 栈的实现
Stack.c
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top; //指向栈顶的位置int capacity; //栈的容量
}ST;//初始化
void StackInit(ST* ps);//入栈——栈顶
void StackPush(ST* ps, STDataType x);//出栈——栈顶
void StackPop(ST* ps);//栈是否为空
bool StackEmpty(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);//获取栈中有效元素个数
int StackSize(ST* ps);//销毁
void StackDestroy(ST* ps);Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void StackPush(ST* 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;
}//栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(ST* ps)
{return ps->top;
}//销毁
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"void test01()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){STDataType top = StackTop(&st);printf("%d ", top);StackPop(&st);}StackDestroy(&st);
}int main()
{test01();return 0;
}1.3 栈的算法题
https://leetcode.cn/problems/valid-parentheses
思路：借助数据结构——栈
遍历字符串，（1）左括号进栈（2）遇到右括号，取栈顶元素与之比较，看是否匹配
//定义栈的结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top; //指向栈顶的位置int capacity; //栈的容量
}ST;//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void StackPush(ST* 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;
}//栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(ST* ps)
{return ps->top;
}//销毁
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}
//---------------------以上是栈的实现代码-------------------
//借助数据结构——栈
bool isValid(char* s)
{ST st;StackInit(&st);char* pi = s;while(*pi != '\0'){//左括号入栈if(*pi == '(' || *pi == '[' || *pi == '{'){StackPush(&st, *pi);}else{//判断栈为空的情况if(StackEmpty(&st)){StackDestroy(&st);return false;}//右括号——取栈顶与*pi进行匹配char top = StackTop(&st);if((top == '(' && *pi != ')') || (top == '[' && *pi != ']') || (top == '{' && *pi != '}')){StackDestroy(&st);return false;}StackPop(&st);}pi++;}bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;
}2、队列
2.1 概念与结构
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出的特点。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。那么，队列底层结构该如何实现呢？如果用数组来实现，那么入队操作时间复杂度为O(1)，出队O(N)。如果用链表来实现，那么入队O(N)，出队O(1)。但是，我们可以定义一个队尾指针pTail来优化，这样入队的时间复杂度就变为O(1)。所以我们采用链表来实现队列。
2.2 队列的实现
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;
//队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size; //队列中有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);//入队——队尾
void QueuePush(Queue* pq, QDataType x);//出队——队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队——队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{//队列非空pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队——队头
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//只有一个结点，phead和ptail都要置为空if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);//第一种方式:遍历链表(适用于不会频繁调用队列有效数据个数的场景)//QueueNode* pcur = pq->phead;//int size = 0;//while (pcur)//{// size++;// pcur = pcur->next;//}//return size;//第二种方式:适用于频繁调用队列有效数据个数的场景return pq->size;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"void test01()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);int front = QueueFront(&q);int rear = QueueBack(&q);printf("front:%d\n", front);printf("rear:%d\n", rear);printf("size:%d\n", QueueSize(&q));
}int main()
{test01();return 0;
}
