4.1栈和队列基本概念+经典OJ题

2024-08-23 05:04
文章标签 经典 队列 基本概念 oj 4.1

本文主要是介绍4.1栈和队列基本概念+经典OJ题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本篇博客来梳理栈和队列基本概念以及一道经典OJ题，题目已插入超链接，点击即可跳转~

一、栈的相关概念

1．栈

一种特殊的线性表，只允许在固定的一端插入和删除元素，栈中的数据遵循后进先出原则

（1）栈顶：进行数据插入和删除操作的一端

（2）栈底：栈顶的另一端

2．压栈：栈的插入操作

3．出栈：栈的删除操作

栈示意图

4．栈的实现：用数组较优，原因是数组尾插代价比较小

（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;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

（2）Stack.c

#include"Stack.h"
void StackInit(Stack* ps)// 初始化栈 
{assert(ps);ps->_a = NULL;ps->_top = 0;ps->_capacity = 0;
}void StackPush(Stack* ps, STDataType data)//入栈(数组的尾插)
{assert(ps);if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->_a,newcapacity * sizeof(STDataType));if (tmp == NULL){perror("malloc failed!");return;}ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top] = data;ps->_top=ps->_top + 1;
}void StackPop(Stack* ps)//出栈（去掉数组最后一个元素）
{assert(ps);assert(ps->_top > 0);ps->_top--;
}STDataType StackTop(Stack* ps)//获取栈顶元素
{assert(ps);assert(ps->_top);return ps->_a[ps->_top-1];
}int StackSize(Stack* ps)//获取栈中有效元素个数
{assert(ps);return ps->_top;
}bool StackEmpty(Stack* ps)// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
{assert(ps);return ps->_capacity == 0;
}void StackDestroy(Stack* ps)//销毁栈
{assert(ps);ps->_capacity =  0;ps->_top = 0;free(ps->_a);ps->_a = NULL;
}

二、队列的相关概念

1．队列

一种特殊的线性表，只允许在一端插入数据，在另一端删除数据，栈中的元素遵循先进先出的原则

2．队头（对应链表头节点）：出队列的一侧

3．队尾（对应链表尾节点）：入队列的一侧

队列示意图

4．队列的实现：用链表较优，原因是数据出队列需要头删，数组效率较低

（1）Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化队列 
void QueueInit(Queue* pq);
// 队尾入队列（尾插） 
void QueuePush(Queue* pq, QDataType data);
// 队头出队列（头删）
void QueuePop(Queue* pq);
// 获取队列头部元素 
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数 
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* pq);
// 销毁队列 
void QueueDestroy(Queue* pq);

（2）Queue.c

#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 队尾入队列 
void QueuePush(Queue* pq, QDataType data)
{assert(pq);if (pq->phead == NULL)//空队列{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed!");return;}newnode->next = NULL;newnode->data = data;pq->phead = newnode;pq->ptail = pq->phead;pq->size++;}else{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed!");return;}newnode->next = NULL;newnode->data = data;pq->ptail->next = newnode;pq->ptail = newnode;pq->size++;}
}// 队头出队列（头删）
void QueuePop(Queue* pq)
{assert(pq);if (pq->phead->next == NULL)//只有一个节点{free(pq->phead);pq->phead = pq->ptail = NULL;pq->size = 0;}else{QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;pq->size--;}
}// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{assert(pq);return pq->phead->data;
}// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{assert(pq);return pq->ptail->data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{return pq->size;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* pq)
{if (pq->size == 0){return 1;}else{return 0;}
}// 销毁队列 
void QueueDestroy(Queue* pq)
{QNode* pcur = pq->phead;while (pcur){QNode* del = pcur;pcur = pcur->next;free(del);del = NULL;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

三、经典OJ：有效的括号

1、题目描述

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

2、题目分析

（1）C语言的限制

由于C语言不直接提供栈，因此需要把我们自己实现的栈粘贴到解决方案当中

（2）思路分析

  • 第一步：遇到的左括号全部入栈
  • 第二步：如果遇到右括号，则把栈顶的左括号出栈，拿出来和右括号匹配
    思路分析

（3）代码实现

如果用C语言实现，请记得在本函数上方粘贴自己实现好的栈，在本函数中才可以调用相关接口~

bool isValid(char* s) 
{Stack stack;StackInit(&stack);while(*s!='\0'){if(*s=='('||*s=='['||*s=='{'){StackPush(&stack,*s);//左括号入栈}else//此时*s是右括号{if(stack._top == 0)//此时栈里面没有左括号{return false;}STDataType left=StackTop(&stack);//取出栈顶元素进行配对if((left=='('&&*s!=')')||(left=='['&&*s!=']')||(left=='{'&&*s!='}')){return false;}else//配对成功，出栈{StackPop(&stack);}}s++;}if(stack._top>0){return false;}return true;
}

这篇关于4.1栈和队列基本概念+经典OJ题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1098426。

相关文章

hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程（Gaussian Process，简称GP）是一种概率模型，用于描述一组随机变量的联合概率分布，其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数（或核函数） 1.3 核函数1.4 高斯过程回归（Gauss
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
【机器学习】高斯网络的基本概念和应用领域

【机器学习】高斯网络的基本概念和应用领域

引言 高斯网络（Gaussian Network）通常指的是一个概率图模型，其中所有的随机变量（或节点）都遵循高斯分布 文章目录 引言一、高斯网络（Gaussian Network）1.1 高斯过程（Gaussian Process）1.2 高斯混合模型（Gaussian Mixture Model）1.3 应用1.4 总结 二、高斯网络的应用2.1 机器学习2.2 统计学2.3
阅读更多...
Java并发编程之——BlockingQueue（队列）

Java并发编程之——BlockingQueue（队列）

一、什么是BlockingQueue BlockingQueue即阻塞队列，从阻塞这个词可以看出，在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种： 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被阻塞，除非有另一个线程做了出队列操作；同样，当一个线程试图对一个空
阅读更多...
HotSpot虚拟机的经典垃圾收集器

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图： 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc
阅读更多...
STL经典案例（四）——实验室预约综合管理系统（项目涉及知识点很全面，内容有点多，耐心看完会有收获的！）

STL经典案例（四）——实验室预约综合管理系统（项目涉及知识点很全面，内容有点多，耐心看完会有收获的！）

项目干货满满，内容有点过多，看起来可能会有点卡。系统提示读完超过俩小时，建议分多篇发布，我觉得分篇就不完整了，失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份：管理员、实验室教师、学生 管理员：给学生和实验室教师创建账号并分发 实验室教师：审核学生的预约申请 学生：申请使用实验室 高校实验室包括：超景深实验室（可容纳10人）、大数据实验室（可容纳20人）、物联网实验
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2