【数据结构】栈与队列

栈

栈的概念及结构

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

在这里插入图片描述

栈的实现

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

在这里插入图片描述
用数组实现：

Stack.h

#pragma once#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>//#define N 10
//struct Stack {
//	int a[N];
//	int top;
//};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);
int STSize(ST* ps);
bool STEmpty(ST* ps);STDataType STTop(ST* ps);

Stack.c

#include "Stack.h"void STInit(ST* ps) {assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL) {perror("malloc fail");return;}ps->capacity = 4;//ps->top = -1;//top栈顶元素位置ps->top = 0;//top栈顶元素下一个位置
}
void STDestroy(ST* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (ps->a == NULL) {perror("malloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
void STPop(ST* ps) {assert(ps);assert(!STEmpty(ps));ps->top--;
}
int STSize(ST* ps) {assert(ps);return ps->top;
}
bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps) {assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

Test.c

#pragma once#include "Stack.h"int main() {ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);//while (!STEmpty(&st)) {while (st.top!=0) {printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);return 0;
}

例1：

在这里插入图片描述
方法：
左括号入栈
右括号于出栈顶的那个左括号匹配
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

队列

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
在这里插入图片描述
Queue.h

#pragma once#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;typedef struct QueueNode {struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue {QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataType x);//尾插
void QueuePop(Queue* pq);//头删
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataType QueueFront(Queue* pq);//队头的数据
QDataType QueueBack(Queue* pq);//队尾的数据

Queue.c

#include "Queue.h"void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq) {assert(pq);QNode* cur = pq->head;while (cur) {QNode* next = cur->next;free(cur);cur = next;}
}void QueuePush(Queue* pq, QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode -> data = x;newnode->next = NULL;if (newnode == NULL) {perror("malloc fail");return;}if (pq->head == NULL) {assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq) {assert(pq);assert(pq->head != NULL);/*QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL) {pq->tail = NULL;}*/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--;
}int QueueSize(Queue* pq) {assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;
}QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

Test.c

#pragma once#include "Queue.h"int main() {Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);while (!QueueEmpty(&q)) {printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}

例2：

在这里插入图片描述
方法：
保持一个队列为空，一个队列存数据
出栈，把前面数据导入空队列

typedef int QDataType;typedef struct QueueNode {struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue {QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq) {assert(pq);QNode* cur = pq->head;while (cur) {QNode* next = cur->next;free(cur);cur = next;}
}void QueuePush(Queue* pq, QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail");return;}newnode -> data = x;newnode->next = NULL;if (pq->head == NULL) {assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq) {assert(pq);assert(pq->head != NULL);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--;
}int QueueSize(Queue* pq) {assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;
}QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);  return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}elseQueuePush(&obj->q2,x);
}int myStackPop(MyStack* obj) {Queue* emptyQ=&obj->q1;Queue* nonemptyQ=&obj->q2;if(!QueueEmpty(emptyQ)){emptyQ=&obj->q2;nonemptyQ=&obj->q1;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int top=QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1))return QueueBack(&obj->q1);elsereturn QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

例3

在这里插入图片描述

分为两个栈，一个进数据pushst，一个出数据popst
当需要出数据时，分为两种情况，
1，popst中没有数据时，需要将pushst的数据导入popst中，此时popst中数据顺序与pushst中相反
正常出数据即可
2.popst中有数据时，正常出数据即可

#pragma once#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>typedef int STDataType;typedef struct Stack {int* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);STDataType STTop(ST* ps);void STInit(ST* ps) {assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL) {perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}
void STDestroy(ST* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (ps->a == NULL) {perror("malloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
void STPop(ST* ps) {assert(ps);assert(!STEmpty(ps));ps->top--;
}
int STSize(ST* ps) {assert(ps);return ps->top;
}
bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps) {assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("malloc fail");return NULL;}STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}int myQueuePop(MyQueue* obj) {int front=myQueuePeek(obj);STPop(&obj->popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}/*** 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);
*/

例4：

在这里插入图片描述

typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->front=obj->rear=0;obj->a=(int*)malloc(sizeof(int)*(k+1));obj->k=k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++]=value;obj->rear%=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->front++;obj->front%=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;else{int x=obj->rear==0?obj->k:obj->rear-1;return obj->a[x];}//return obj->a[(obj->rear-1+obj->k+1)%(obj->k+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);
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/12533.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

安全实验作业

安全实验作业

一 拓扑图 二 要求 1、R4为ISP&#xff0c;其上只能配置IP地址&#xff1b;R4与其他所有直连设备间均使用共有IP 2、R3-R5-R6-R7为MGRE环境&#xff0c;R3为中心站点&#xff1b; 3、整个OSPF环境IP基于172.16.0.0/16划分&#xff1b; 4、所有设备均可访问R4的环回&#x…
阅读更多...
e2studio开发RA4M2(6)----GPIO外部中断（IRQ）配置

e2studio开发RA4M2(6)----GPIO外部中断（IRQ）配置

e2studio开发RA4M2.6--GPIO外部中断&#xff08;IRQ&#xff09;配置 概述视频教学样品申请硬件准备参考程序源码下载新建工程工程模板保存工程路径芯片配置工程模板选择时钟设置SWD调试口设置GPIO口配置按键中断配置中断回调函数主程序 概述 GPIO&#xff08;通用输入/输出&a…
阅读更多...
排序算法--快速排序

排序算法--快速排序

快速排序是高效的排序算法&#xff0c;平均时间复杂度为 O(nlog⁡n)&#xff0c;适合大规模数据排序。 1.挖坑法 2左右指针法 3.前后指针法 // 交换两个元素的值 void swap(int* a, int* b) {int temp *a;*a *b;*b temp; }// 分区函数&#xff0c;返回分区点的索引 int par…
阅读更多...
分享｜LLM通过D-E-P-S完成长时间与多步骤的任务

分享｜LLM通过D-E-P-S完成长时间与多步骤的任务

《Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents&#xff1f; 描述、解释、计划和选择&#xff1a;使用大型语言模型进行交互式规划&#xff0c;实现开放世界的多任务代理 问题背景&#xff1a;…
阅读更多...
chrome浏览器chromedriver下载

chrome浏览器chromedriver下载

chromedriver 下载地址 https://googlechromelabs.github.io/chrome-for-testing/ 上面的链接有和当前发布的chrome浏览器版本相近的chromedriver 实际使用感受 chrome浏览器会自动更新&#xff0c;可以去下载最新的chromedriver使用&#xff0c;自动化中使用新的chromedr…
阅读更多...
swagger使用指引

swagger使用指引

1.swagger介绍 在前后端分离开发中通常由后端程序员设计接口&#xff0c;完成后需要编写接口文档&#xff0c;最后将文档交给前端工程师&#xff0c;前端工程师参考文档进行开发。 可以通过一些工具快速生成接口文档 &#xff0c;本项目通过Swagger生成接口在线文档 。 什么…
阅读更多...
一文速览DeepSeek-R1的本地部署——可联网、可实现本地知识库问答：包括671B满血版和各个蒸馏版的部署

一文速览DeepSeek-R1的本地部署——可联网、可实现本地知识库问答：包括671B满血版和各个蒸馏版的部署

前言 自从deepseek R1发布之后「详见《一文速览DeepSeek R1&#xff1a;如何通过纯RL训练大模型的推理能力以比肩甚至超越OpenAI o1(含Kimi K1.5的解读)》」&#xff0c;deepseek便爆火 爆火以后便应了“人红是非多”那句话&#xff0c;不但遭受各种大规模攻击&#xff0c;即便…
阅读更多...
低通滤波算法的数学原理和C语言实现

低通滤波算法的数学原理和C语言实现

目录 概述 1 原理介绍 1. 1 基本概念 1.2 一阶RC低通滤波器模型 2 C语言完整实现 2.1 滤波器结构体定义 2.2 初始化函数 2.3 滤波计算函数 3 应用示例 3.1 噪声信号滤波 3.2 输出效果对比 3.3 关键参数选择指南 4 性能优化技巧 4.1 定点数优化 4.2 抗溢出处理 …
阅读更多...
自研有限元软件与ANSYS精度对比-Bar3D2Node三维杆单元模型-央视大裤衩实例

自研有限元软件与ANSYS精度对比-Bar3D2Node三维杆单元模型-央视大裤衩实例

目录 1、“央视大裤衩”自研有限元软件求解 1.1、选择单元类型 1.2、导入“央视大裤衩”工程 1.3、节点坐标定义 1.4、单元连接关系、材料定义 1.5、约束定义 1.6、外载定义 1.7、矩阵求解 1.8、变形云图展示 1.9、节点位移 1.10、单元应力 1.11、节点支反力 2、“…
阅读更多...
Hot100之堆

Hot100之堆

我们的PriorityQueue默认为最小堆&#xff0c;堆顶总是为最小 215数组中的第K个最大元素 题目 思路解析 暴力解法&#xff08;不符合时间复杂度&#xff09; 题目要求我们找到「数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素」。「数组排序后的第 k …
阅读更多...
FinRobot：一个使用大型语言模型的金融应用开源AI代理平台

FinRobot：一个使用大型语言模型的金融应用开源AI代理平台

“FinRobot: An Open-Source AI Agent Platform for Financial Applications using Large Language Models” 论文地址&#xff1a;https://arxiv.org/pdf/2405.14767 Github地址&#xff1a;https://github.com/AI4Finance-Foundation/FinRobot 摘要 在金融领域与AI社区间&a…
阅读更多...
算法题（57）：找出字符串中第一个匹配项的下标

算法题（57）：找出字符串中第一个匹配项的下标

审题: 需要我们根据原串与模式串相比较并找到完全匹配时子串的第一个元素索引&#xff0c;若没有则返回-1 思路&#xff1a; 方法一&#xff1a;BF暴力算法 思路很简单&#xff0c;我们用p1表示原串的索引&#xff0c;p2表示模式串索引。遍历原串&#xff0c;每次遍历都匹配一次…
阅读更多...
「全网最细 + 实战源码案例」设计模式——策略模式

「全网最细 + 实战源码案例」设计模式——策略模式

核心思想 策略模式&#xff08;Strategy Pattern&#xff09;是一种行为型设计模式&#xff0c;用于定义一系列算法或策略&#xff0c;将它们封装成独立的类&#xff0c;并使它们可以相互替换&#xff0c;而不影响客户端的代码&#xff0c;提高代码的可维护性和扩展性。 结构 …
阅读更多...
linux 进程补充

linux 进程补充

环境变量 基本概念 环境变量(environment variables)一般是指在操作系统中用来指定操作系统运行环境的一些参数 如&#xff1a;我们在编写C/C代码的时候&#xff0c;在链接的时候&#xff0c;从来不知道我们的所链接的动态静态库在哪 里&#xff0c;但是照样可以链接成功&#…
阅读更多...
排序算法--选择排序

排序算法--选择排序

选择排序虽然简单&#xff0c;但时间复杂度较高&#xff0c;适合小规模数据或教学演示。 // 选择排序函数 void selectionSort(int arr[], int n) {for (int i 0; i < n - 1; i) { // 外层循环控制当前最小值的存放位置int minIndex i; // 假设当前位置是最小值的索引// 内…
阅读更多...
java求职学习day27

java求职学习day27

数据库连接池 &DBUtils 1.数据库连接池 1.1 连接池介绍 1) 什么是连接池 实际开发中 “ 获得连接 ” 或 “ 释放资源 ” 是非常消耗系统资源的两个过程&#xff0c;为了解决此类性能问题&#xff0c;通常情况我们 采用连接池技术&#xff0c;来共享连接 Connection 。…
阅读更多...
接入DeepSeek大模型

接入DeepSeek大模型

接入DeepSeek 下载并安装Ollamachatbox 软件配置大模型 下载并安装Ollama 下载并安装Ollama&#xff0c; 使用参数ollama -v查看是否安装成功。 输入命令ollama list&#xff0c; 可以看到已经存在4个目录了。 输入命令ollama pull deepseek-r1:1.5b&#xff0c; 下载deepse…
阅读更多...
AI大模型（二）基于Deepseek搭建本地可视化交互UI

AI大模型（二）基于Deepseek搭建本地可视化交互UI

AI大模型&#xff08;二&#xff09;基于Deepseek搭建本地可视化交互UI DeepSeek开源大模型在榜单上以黑马之姿横扫多项评测&#xff0c;其社区热度指数暴涨、一跃成为近期内影响力最高的话题&#xff0c;这个来自中国团队的模型向世界证明&#xff1a;让每个普通人都能拥有媲…
阅读更多...
防火墙安全策略实验

防火墙安全策略实验

一、实验拓扑图及实验要求 实验要求&#xff1a; 1、VLAN2属于办公区&#xff1b;VLAN 3属于生产区。 2、办公区PC在工作日时间&#xff08;周一至周五&#xff0c;早8到晚6)可以正常访问0A Server&#xff0c;其他时间不允许。 3、办公区可以在任意时刻访问web Server 4、生产…
阅读更多...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】3.1 NumPy图像大小调整实战

【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】3.1 NumPy图像大小调整实战

3.1 NumPy图像大小调整实战 目录 #mermaid-svg-uDg4hyooC74c0r2r {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-uDg4hyooC74c0r2r .error-icon{fill:#552222;}#mermaid-svg-uDg4hyooC74c0r2r .error-text{fill:#5…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023