当前位置： 首页 > news >正文

数据结构——栈和队列

news 2025/8/17 3:49:42

在这里插入图片描述

栈和队列的建立

  • 前言
  • 一、栈
    • 1.栈的概念
    • 2.栈的实现
    • 3.代码示例
      • （1）Stack.h
      • （2）Stack.c
      • （3）Test.c
      • （4）运行结果
      • （5）完整代码演示
  • 二、队列
    • 1.队列的概念
    • 2.队列的实现
    • 3.代码示例
      • （1）Queue.h
      • （2）Queue.c
      • （3）Test.c
      • （4）运行结果
      • （5）完整代码演示
  • 三、栈的应用例题
    • 方法一
    • 方法二
  • 总结

前言

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

一、栈

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;
}

总结

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

http://www.lryc.cn/news/136336.html

相关文章：

  • 苍穹外卖阿里云oss存储笔记
  • Kafka 集群搭建过程
  • 【算法随记】在计算过程中模的情况
  • MSTP多生成树协议（第二课）
  • 数组指针、函数指针、指针数组、函数 指针数组、指针函数详细总结
  • Linux存储学习笔记
  • ubuntu执行jmeter端口不够用报错(Address not available)
  • MongoDB:简单的增删改查操作
  • 网络编程（域套接字）
  • 探索短视频小程序/小年糕
  • 基于MATLAB开发AUTOSAR软件应用层Code mapping专题-part 7 Function callers标签页介绍
  • ARM开发（cortex-A7核中断实验)
  • 关于融合项目点云pointpillars检测不显示三维检测框问题的解决
  • spring复习：（57）PropertyOverrideConfigurer用法及工作原理
  • 在axios中获取文件上传进度
  • 黑马头条-kafka配置
  • PMP P-01 Basic Knowledge
  • java八股文面试[数据结构]——ArrayList和LinkedList区别
  • OpenCV中QR二维码的生成与识别(CIS摄像头解析)
  • 常见排序集锦-C语言实现数据结构
  • css 实现四角边框样式
  • 机器学习深度学习——自注意力和位置编码（数学推导+代码实现）
  • 02.案列项目Demo
  • PDF校对：追求文档的精准与完美
  • 低代码解放生产力，助力企业高效发展
  • 【前端从0开始】CSS——9、浮动
  • 如何在Moonriver网络上向社区代表委托投票权利
  • 时序预测 | MATLAB实现基于CNN-GRU卷积门控循环单元的时间序列预测-递归预测未来(多指标评价)
  • 【李群李代数】李群控制器（lie-group-controllers）介绍——控制 SO(3) 空间中的系统的比例控制器Demo...
  • DP读书：鲲鹏处理器 架构与编程（六）PCI Express 总线