数据结构——栈和队列

---

前言

今天我们来学习栈和队列的简易建立！
在后面还会有一道栈的应用题，检测大家的用功程度！
加油吧！

---

一、栈

1.栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

模型图示例：

2.栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

图片示例：

3.代码示例

（1）Stack.h

1.头文件的声明

//头文件的声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

2.栈的接口定义

//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

3.初始化和销毁函数的声明

//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);

4.入栈和出栈函数的声明

//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);

5.查找栈顶元素和长度计算函数以及判空函数的声明

//插入
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);

（2）Stack.c

1.头文件的声明

#include "Stack.h"

2.初始化和销毁函数的定义

/初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

3.入栈和出栈函数的定义

//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);--ps->top;
}

4.查找栈顶元素和长度计算函数以及判空函数的定义

//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps->top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

（3）Test.c

1.头文件的声明

#include "Stack.h"

2.测试函数的定义

void TestStack()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STPush(&st, 6);STPush(&st, 7);STPush(&st, 8);STPush(&st, 9);STPush(&st, 10);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestroy(&st);
}

3.主函数的定义

int main()
{TestStack();return 0;
}

（4）运行结果

（5）完整代码演示

1.Stack.h

#pragma once
//头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);

2.Stack.c

#include "Stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);--ps->top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps->top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

3.Test.c

#include "Stack.h"void TestStack1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STPush(&st, 6);STPush(&st, 7);STPush(&st, 8);STPush(&st, 9);STPush(&st, 10);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestroy(&st);
}int main()
{TestStack1();return 0;
}

二、队列

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

模型图示例：

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

图片示例：

3.代码示例

（1）Queue.h

1.头文件的声明

#pragma once
//头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

2.队列接口的定义

//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;

3.初始化和销毁函数的声明

//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);

4.入队列和出队列函数的声明

//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);

5.查找队头、查找队尾函数的声明

//查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);

6.判空以及长度计算函数的声明

//判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq);

（2）Queue.c

1.头文件的声明

#include "Queue.h"

2.初始化和销毁函数的定义

void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

3.入队列和出队列函数的定义

void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}

4.查找队头、查找队尾函数的定义

//查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//查找队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

5.判空以及长度计算函数的定义

//判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}//长度计算
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

（3）Test.c

1.头文件的声明

#include "Queue.h"

2.测试函数的定义

void QueueTest() {Que pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 5);while (!QueueEmpty(&pq)) {printf("%d ", QueueFront(&pq));QueuePop(&pq);}QueueDestroy(&pq);
}

3.主函数的定义

int main() {QueueTest();return 0;
}

（4）运行结果

（5）完整代码演示

1.Queue.h

#pragma once
//头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);
//查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);
//判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq);

2.Queue.c

#include "Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//查找队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}//长度计算
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

3.Test.c

#include "Queue.h"void QueueTest() {Que pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 5);while (!QueueEmpty(&pq)) {printf("%d ", QueueFront(&pq));QueuePop(&pq);}QueueDestroy(&pq);
}int main() {QueueTest();return 0;
}

三、栈的应用例题

题目：括号匹配问题
题目链接

提示：
. 1 <= s.length <= 104
. s 仅由括号 ‘()[]{}’ 组成

解题思路：
这道题我有两种解法！
建栈法和暴力破解法！

方法一

首先第一种就是利用栈来解决：
1.左括号，入栈；
2.右括号与栈中的栈顶括号进行匹配；

图例：

代码示例：

引用之前栈的建立函数：

//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);--ps->top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps->top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

功能函数的定义

bool isValid(char* s) {ST st;STInit(&st);char topVal;while (*s ) {if (*s == '(' || *s == '[' || *s == '{') {STPush(&st, *s);}else {//数量不匹配if (STEmpty(&st)){STDestroy(&st);return false;}topVal = STTop(&st);STPop(&st);if ((*s == ']' && topVal != '[')|| (*s == ']' && topVal != '[')|| (*s == ']' && topVal != '[')) {STDestroy(&st);return false;}}++s;}bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

方法二

第二种方法就是例子中如果不存在无效括号的话，那么至少有一个是左右括号相邻的；
所以先找到相邻且匹配的括号将其移除，然后慢慢一点一点全部都移除的话则说明全部括号有效！

图例

代码演示：

bool isValid(char* s) {char* p = s;while (*p) {p = s;while (*p) {if (*p + 1 == *(p + 1) || *p + 2 == *(p + 1)) {//查看assii码表了解符号的大小char* move = p;while (true) {*move = *(move + 2);if(*move=='\0')break;move++;}break;}else {p++;}}if (*p == '\0' && *s != '\0')return false;}return true;
}

---

总结

今天的内容有点多，希望大家仔细观看，细细揣摩！
好好学习，天天向上！
不变的真理！