栈

栈是什么，栈是一种数据存储的结构，采用的是先进后出，后进先出的原则，就好像是弹匣里的子弹，比如说一个弹匣有30发容量，那第一个发压进去的子弹肯定是最后一个射出的，最先射出的子弹肯定是最后压入弹匣的。
往栈里放入数据叫做压栈，从栈里出数据叫做出栈，我们用弹匣来举例，一个压满子弹的弹匣，第一个压入的子弹在弹匣的最底部，最后一个压人弹匣的子弹在最顶部，栈最先放入的数据所在的位置叫做栈底，栈最后放人的数据的位置叫做栈顶：

如图所示，栈底的元素是1，栈顶的元素是6
栈只支持在固定的一端插入和删除数据，进行删除和插入的一端叫做栈顶，另一端叫做栈底

栈的实现：

头文件 Stack.h：

#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>// 支持动态增长的栈
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps);// 入栈 
void StackPush(Stack* ps, STDataType data);// 出栈 
void StackPop(Stack* ps);// 获取栈顶元素 
STDataType StackTop(Stack* ps);// 获取栈中有效元素个数 
int StackSize(Stack* ps);// 检测栈是否为空，如果为空true，如果不为空返回false
bool StackEmpty(Stack* ps);// 销毁栈 
void StackDestroy(Stack* ps);

函数的实现 Stack.c：

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);//初始化为栈申请4个字节的空间STDataType* a = (STDataType*)malloc(sizeof(STDataType) * 4);if (a == NULL){perror("malloc");exit(-1);}ps->a = a;//数组ps->capacity = 4;//容量ps->top = 0;//栈顶下标}// 入栈 
void StackPush(Stack* ps, STDataType data)
{//断言assert(ps);//判断容量是否够用if (ps->capacity == ps->top){//不够扩容//扩容到之前容量的两倍STDataType* a = (STDataType*)realloc(ps->a,sizeof(STDataType) * (ps->capacity * 2));if (a == NULL){perror("malloc");exit(-1);}}//使用栈顶top作为下标进行压栈ps->a[ps->top] = data;//将top++，作为下一次压栈的下标，同时也代表着现在栈里有多少个元素ps->top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);//判断栈是否为空if (StackEmpty(ps)){printf("栈为空\n");exit(-1);}//将栈顶的元素移除//将top--，这样就访问不到栈顶的元素，而是将栈顶位置往下移了一个位置ps->top--;}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);//判断栈是否为空if (StackEmpty(ps)){printf("栈为空\n");exit(-1);}//top记录的是栈顶下一个位置//比如说top是0，当进行压栈的时候，0的位置压入数据变成栈顶//然后top++，为下一个入栈做准备//所以top--才是栈顶的元素//如果不想用--这个操作，初始化的时候将top初始化成-1即可return ps->a[ps->top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);//判断栈是否为空if (StackEmpty(ps)){printf("栈为空\n");exit(-1);}//这里也可以不用判断栈是否为空//当栈为空，top就是0，返回0也可以//top记录就是元素的个数return ps->top;
}// 检测栈是否为空，如果为空true，如果不为空返回false
bool StackEmpty(Stack* ps)
{assert(ps);//初始化栈为空，记录栈顶个数的top也为空//每次入栈top++，每次出栈top--//所以当top为空时，栈就为空return ps->top == 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);//将栈释放free(ps->a);ps->a = NULL;//将容量和元素个数全部置为0ps->capacity = ps->top = 0;
}

主函数 test.c：

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"void mune()
{printf("********************************\n");printf("******1，压栈     2，出栈  *****\n");printf("******3，获取栈顶元素      *****\n");printf("******4，获取栈中有效元素的个数*\n");printf("******5，销毁栈            *****\n");printf("******6，判断栈是否为空    *****\n");printf("******0，退出（EXIT）      *****\n");printf("********************************\n");
}int main()
{//创建栈并初始化Stack ST;StackInit(&ST);STDataType input = 0;do{//打印菜单mune();printf("请根据提示选择对应的功能：>");scanf("%d",&input);switch (input){case 1://压栈printf("输入要压栈的元素:>\n");STDataType i = 0;scanf("%d",&i);StackPush(&ST,i);printf("入栈成功,栈里有效元素%d个\n", StackSize(&ST));break;case 2://出栈//获取栈顶元素printf("栈顶元素%d出栈成功\n", StackTop(&ST));//出栈StackPop(&ST);printf("栈里有效元素%d个\n", StackSize(&ST));break;case 3://获取栈顶元素printf("栈顶元素为%d\n", StackTop(&ST));break;case 4://获取栈里有效元素个数printf("栈里有效元素%d个\n", StackSize(&ST));break;case 5://销毁栈StackDestroy(&ST);printf("栈销毁成功\n");break;case 6://判断栈是否为空if (StackEmpty(&ST)){printf("栈为空,元素个数为%d\n", StackSize(&ST));}else{printf("栈不为空,元素个数为%d\n", StackSize(&ST));}break;case 0:printf("退出成功！！！\n");exit(-1);break;default:printf("选择错误，请重新选择:>\n");break;}} while (input);return 0;
}

队列

队列的概念和栈相反，先进先出，后进后出，比如说去排队左核酸，第一个排队的第一个做核酸，最后一个排队的最后最后做核酸，达到一个排队的效果。
队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列的插入删除，在实现上和链表的头插尾删非常相似

队列的实现：

创建一个结构体，结构体里放两个栈指针，初始化时将两个指针置为NULL,在第一次进行入队时，创建一个栈，将栈的第一个数据赋给两个指针，此后入队只需创建新节点然后和尾部指针相连，出队将头部指针销毁，然后将头部指针指向下一个节点，一直保持front指向队头，rear指向队尾

头文件声明 Queue.h：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{QDataType data;//数据struct QListNode* next;//下一个节点
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;//队列头部QNode* rear;//队列尾部int size;//记录元素个数
}Queue;// 初始化队列 
void QueueInit(Queue* q);// 队尾入队列 
void QueuePush(Queue* q, QDataType data);// 队头出队列 
void QueuePop(Queue* q);// 获取队列头部元素 
QDataType QueueFront(Queue* q);// 获取队列队尾元素 
QDataType QueueBack(Queue* q);// 获取队列中有效元素个数 
int QueueSize(Queue* q);// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* q);// 销毁队列 
void QueueDestroy(Queue* q);

函数的实现 Queue.c：

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"// 初始化队列 
void QueueInit(Queue* q)
{assert(q);//全部初始化为空q->front = NULL;q->rear = NULL;q->size = 0;
}// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);//申请空间QNode* p = (QNode*)malloc(sizeof(QNode));if (p == NULL){perror("malloc");exit(-1);}//将值赋给pp->data = data;p->next = NULL;//第一次入队列if (q->front == NULL){//第一次入队，两个指针同时指向栈底q->front = q->rear = p;}else{//将尾部的next和新节点连接q->rear->next = p;q->rear = p;}q->size++;
}// 队头出队列 
void QueuePop(Queue* q)
{assert(q);//判断是否只有一个节点if (q->front == q->rear){q->front = NULL;q->rear = NULL;}else{//保留头部QNode* p = q->front;q->front = q->front->next;//释放头部free(p);}q->size--;}// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);//判断队列是否为空if (QueueEmpty(q)){printf("队列为空\n");exit(-1);}//返回队头指针的数据return q->front->data;}// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);//判断队列是否为空if (QueueEmpty(q)){printf("队列为空\n");exit(-1);}//返回队尾指针的数据return q->rear->data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* q)
{assert(q);//这里可以加上数据个数和尾部指针，也可以不加//保险一定可以都加上return q->front == NULL && q->rear == NULL && q->size == 0;
}// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);while (q->front){//保留上一个节点，再销毁下一个节点QNode* p = q->front;q->front = q->front->next;free(p);}q->size = 0;q->rear = NULL;
}

主函数 test.c：

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void menu()
{printf("**************************************\n");printf("*****1，入队列       2，出队列    ****\n");printf("*****3，获取头部元素 4，获取尾部元素**\n");printf("*****5，获取有效元素个数          ****\n");printf("*****6，判断队列是否为空          ****\n");printf("*****7，销毁队列     0，退出      ****\n");printf("**************************************\n");
}int main()
{//创建队列初始化Queue Q;QueueInit(&Q);int input = 0;QDataType i = 0;do{//打印菜单menu();printf("请输入序号进行操作：>");scanf("%d",&input);switch (input){case 1://入队列printf("请输入要入队的值:>\n");scanf("%d",&i);QueuePush(&Q,i);printf("%d入队成功，队列有效元素为%d\n",i, QueueSize(&Q));break;case 2://出队列i = QueueFront(&Q);QueuePop(&Q);printf("队头元素%d出队列成功，队列有效元素为%d\n",i, QueueSize(&Q));break;case 3://获取队头元素printf("队头元素为%d\n", QueueFront(&Q));break;case 4://获取队尾元素printf("队尾元素为%d\n", QueueBack(&Q));break;case 5://获取队列有效元素printf("队列有效元素为%d\n", QueueSize(&Q));break;case 6://判断队列是否为空if (QueueEmpty(&Q)){printf("队列为空\n");}else{printf("队列不为空，元素个数为%d\n", QueueSize(&Q));}break;case 7:// 销毁队列 QueueDestroy(&Q);int j = QueueSize(&Q);if (QueueEmpty(&Q) == NULL && j == 0){printf("队列销毁成功\n");}break;case 0:printf("退出成功！！！\n");return 0;break;default:printf("输入错误，请重新输入\n");break;}} while (input);return 0;
}

力扣笔试题

1，链接: 匹配括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

只要是左括号就入栈，遇到右括号就将栈顶的左括号和右括号匹配


如果中途有一个不匹配直接return false
如果匹配上了，栈顶出元素，s++，进行下一个的匹配

typedef char STDataType;typedef struct Stack
{STDataType* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;// 检测栈是否为空，如果为空true，如果不为空返回false
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}// 初始化栈 
void StackInit(Stack* ps)
{//初始化为栈申请4个字节的空间STDataType* a = (STDataType*)malloc(sizeof(STDataType) * 4);if (a == NULL){perror("malloc");exit(-1);}ps->a = a;//数组ps->capacity = 4;//容量ps->top = 0;//栈顶下标
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->capacity == ps->top){STDataType* a = (STDataType*)realloc(ps->a,sizeof(STDataType) * (ps->capacity * 2));if (a == NULL){perror("malloc");exit(-1);}ps->a = a;ps->capacity *= 2;}ps->a[ps->top] = data;ps->top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);if (StackEmpty(ps)){printf("栈为空\n");exit(-1);}ps->top--;}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);if (StackEmpty(ps)){printf("栈为空\n");exit(-1);}return ps->a[ps->top - 1];
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);//将栈释放free(ps->a);ps->a = NULL;//将容量和元素个数全部置为0ps->capacity = ps->top = 0;
}bool isValid(char * s){//创建栈并初始化Stack ST;StackInit(&ST);while(*s){//左括号入栈if(*s == '(' || *s == '{' || *s == '['){//入栈StackPush(&ST,*s);}//否则就是遇到左括号，进行匹配else{//判断是否一直都是右括号，这样栈里就不会有元素//不会有元素就匹配不上if(StackEmpty(&ST)){return false;}//保留栈顶元素char tmp = StackTop(&ST);//出栈StackPop(&ST);//是右括号就和栈顶元素匹配if((*s == '}' && tmp != '{')||(*s == ')' && tmp != '(')||(*s == ']' && tmp != '[')){//销毁栈StackDestroy(&ST);return false;}}//s++寻找下一个s++;}printf("结束\n");bool tf = StackEmpty(&ST);return tf;
}

这里强调一个特殊情况：

2，链接: 使用两个队列实现先进先出

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{QDataType data;//数据struct QListNode* next;//下一个节点
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;//队列头部QNode* rear;//队列尾部int size;//记录元素个数
}Queue;// 初始化队列 
void QueueInit(Queue* q);// 队尾入队列 
void QueuePush(Queue* q, QDataType data);// 队头出队列 
void QueuePop(Queue* q);// 获取队列头部元素 
QDataType QueueFront(Queue* q);// 获取队列队尾元素 
QDataType QueueBack(Queue* q);// 获取队列中有效元素个数 
int QueueSize(Queue* q);// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* q);// 销毁队列 
void QueueDestroy(Queue* q);// 初始化队列 
void QueueInit(Queue* q)
{assert(q);//全部初始化为空q->front = NULL;q->rear = NULL;q->size = 0;
}// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);//申请空间QNode* p = (QNode*)malloc(sizeof(QNode));if (p == NULL){perror("malloc");exit(-1);}//将值赋给pp->data = data;p->next = NULL;//第一次入队列if (q->front == NULL){//第一次入队，两个指针同时指向栈底q->front = q->rear = p;}else{//将尾部的next和新节点连接q->rear->next = p;q->rear = p;}q->size++;
}// 队头出队列 
void QueuePop(Queue* q)
{assert(q);//判断是否只有一个节点if (q->front == q->rear){q->front = NULL;q->rear = NULL;}else{//保留头部QNode* p = q->front;q->front = q->front->next;//释放头部free(p);}q->size--;}// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);//判断队列是否为空if (QueueEmpty(q)){printf("队列为空\n");exit(-1);}//返回队头指针的数据return q->front->data;}// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);//判断队列是否为空if (QueueEmpty(q)){printf("队列为空\n");exit(-1);}//返回队尾指针的数据return q->rear->data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* q)
{assert(q);//这里可以加上数据个数和尾部指针，也可以不加//保险一定可以都加上return q->front == NULL && q->rear == NULL && q->size == 0;
}// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);while (q->front){//保留上一个节点，再销毁下一个节点QNode* p = q->front;q->front = q->front->next;free(p);}q->size = 0;q->rear = NULL;
}typedef struct {Queue pus;Queue pop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//初始化队列QueueInit(&obj->pus);QueueInit(&obj->pop);return obj;
}//入队
void myQueuePush(MyQueue* obj, int x) {//入队只往pus中入QueuePush(&obj->pus,x);
}//返回队头元素
int myQueuePeek(MyQueue* obj) {//如果pop中有数据，将pop队头数据返回即可//如果pop中没有数据if(QueueEmpty(&obj->pop)){//将pus中的数据全部导入popwhile(!QueueEmpty(&obj->pus)){//导入QueuePush(&obj->pop,QueueFront(&obj->pus));//删除pus头数据QueuePop(&obj->pus);}}//返回pop队头数据return QueueFront(&obj->pop);
}//移除队头并返回
int myQueuePop(MyQueue* obj) {//先调用peek函数，来确保pop中有数据int i = myQueuePeek(obj);//保留队头数据QueuePop(&obj->pop);//让队头出队列return i;
}//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {//如果两条队列都为空返回truereturn QueueEmpty(&obj->pus) && QueueEmpty(&obj->pop);
}//销毁队列
void myQueueFree(MyQueue* obj) {QueueDestroy(&obj->pus);QueueDestroy(&obj->pop);free(obj);obj = NULL;}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

3，链接: 循环队列

typedef struct {int* a;//数组int frond;//头int rear;//尾int k;//数组大小
} MyCircularQueue;//创建并初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (k+1));//多开一个空间obj->frond = 0;obj->rear = 0;obj->k = k;return obj;
}
//检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//当两个下标相同时为空return obj->frond == obj->rear;
}
//检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {//第一种情况，rear在最后一个位置，frond在0的位置if(obj->rear == obj->k && obj->frond == 0){return true;}//第二种情况，rear+1等于frondelse if(obj->rear+1 == obj->frond){return true;}return false;// return (obj->rear+1) % (obj->k+1) == obj->frond;
}
//插入元素，成功返回true
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断是否为满if(myCircularQueueIsFull(obj)){return false;}//先将数据放在rear的位置obj->a[obj->rear] = value;//当rear在最后的位置，让rear回到0的位置if(obj->rear == obj->k){obj->rear = 0;return true;}//rear向后挑一部obj->rear++;return true;
}
//删除元素，成功返回true
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判读是否为空if(myCircularQueueIsEmpty(obj)){return false;}//frond在最后的位置，+1让reond回到0if(obj->frond == obj->k){obj->frond = 0;return true;}obj->frond++;return true;}
//获取队头元素，如果队列为空返回-1
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->frond];
}
//获取队尾元素，队列为空返回-1
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//rear记录的是下一次插入元素的位置//所以上一次插入元素的位置是rear-1if(obj->rear == 0){return obj->a[obj->k];}return obj->a[obj->rear-1];
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/