栈和队列经典面试题

article/2025/9/17 5:49:45

目录

1、括号匹配问题

2、用队列实现栈

3、用栈实现队列

4、设计循环队列


1、括号匹配问题

  • 链接直达:

有效的括号

  • 题目:

  • 思路:

做题前,得先明确解题方案是啥,此题用栈的思想去解决是较为方便的,栈明确指出后进先出。我们可以这样设定:

  1. 遇到左括号( ”、“ [ ”、“ { 入栈
  2. 遇到右括号) ”、“ ] ”、“ }出栈,跟左括号进行匹配,不匹配就报错。

上两句话的意思就是说我去遍历字符串,如果遇到左括号,就入栈;遇到右括号,就出栈顶元素,并判断这个右括号是否与栈顶括号相匹配,若不匹配则返回false,匹配继续遍历字符串,直到遍历完全,遍历后,检查栈是否为空,若为空,则均匹配,返回true,反之false。

  •  代码如下:
//创建栈结构
typedef char STDataType;
typedef struct Stack
{STDataType* a; //存储数据int top; //栈顶的位置int capacity; //容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
//有效元素个数
int StackSize(ST* ps);//定义:
//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//如果栈满了,考虑扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newcapacity; //更新容量}ps->a[ps->top] = x;//将数据压进去ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0; //如果top为0,那么就为真,即返回
}
//访问栈顶数据
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
//有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}//创建好了栈开始实现
bool isValid(char* s) {ST st;//先创建一个栈StackInit(&st);//初始化栈while (*s){if (*s == '[' || *s == '(' || *s == '{'){StackPush(&st, *s); //如果是左括号就入栈++s;}else{if (StackEmpty(&st)){return false; //此处说明前面根本没有左括号,导致栈为空,直接返回false}char top = StackTop(&st); //获取栈顶元素StackPop(&st); //出栈顶元素,接下来进行匹配if ((*s == ']' && top != '[')|| (*s == ')' && top != '(')|| (*s == '}' && top != '{')){StackDestory(&st); //返回前先销毁,防止内存泄漏return false; //如果不匹配,直接返回false}else{//此时匹配,继续比较,直到遍历结束++s;}}}//栈为空,说明所有左括号都匹配bool ret = StackEmpty(&st);StackDestory(&st); //返回前先销毁,防止内存泄漏return ret;
}

2、用队列实现栈

  • 链接直达:

用队列实现栈

  • 题目:

  •  思路:

做题之前,再明确下两个基本知识点

  1. 栈:后进先出
  2. 队列:先进先出

此题要用先进先出的队列来实现后进先出的栈,并模拟实现队列的基本接口。

假设我们有一串数字,进入队列A顺序为1 2 3 4,此时再有一个队列B,此时我们取队列A的队头数据,并将其导入队列B,当队列A出到只剩最后一个时,把队列A给pop删掉,此时队列B就是1 2 3,间接性是实现了栈的功能,实现了后进先出的功能。当我们需要再入数据时,只需往不为空的队列入即可。再出就像刚刚那样。简而言之两句话:

  1. 入栈:push数据到不为空的队列。
  2. 出栈:把不为空的队列的数据前N-1导入另一个空队列,最后剩下一个删掉。

本质:保持一个队列存储数据,另外一个队列空着,要出栈时,空队列用来导数据。

  •  代码如下:
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型,本文以int为例//创建队列节点
typedef struct QueueNode
{QDataType data; //存储数据struct QueueNode* next; //记录下一个节点
}QNode;
//保存队头和队尾
typedef struct Queue
{QNode* head; //头指针QNode* tail; //尾指针
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//获取有效元素个数
size_t QueueSize(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);//定义:
//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建一个新节点保存数据QNode* newnode = (QNode*)malloc(sizeof(QNode));//暴力检测newnode,因为malloc的都要检测assert(newnode);newnode->next = NULL;newnode->data = x;//如果一开始没有数据,为空的情况if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head && pq->tail); //tail和head均不能为空//特殊:当删到head=tail的位置时if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}//一般情况else{//保存head的下一个节点QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
//获取有效元素个数
size_t QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;
}
//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head); //头部不能为空return pq->head->data;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->tail); //尾部不能为空return pq->tail->data;
}/**************创建好队列结构,开始正文模拟实现栈**************/
typedef struct {Queue q1; //队列q1Queue q2; //队列q2
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); //申请一个MyStack类型的栈assert(pst);QueueInit(&pst->q1);//初始化队列1QueueInit(&pst->q2);//初始化队列2return pst;
}void myStackPush(MyStack* obj, int x) {assert(obj);if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);//如果q1不为空,就往q1插入数据}else{QueuePush(&obj->q2, x);//这儿不需要知道q2是否为空,直接push}
}int myStackPop(MyStack* obj) {assert(obj);Queue* emptyQ = &obj->q1; //默认q1为空Queue* nonEmtpyQ = &obj->q2;//默认q2不为空if (!QueueEmpty(&obj->q1)){emptyQ = &obj->q2; //若假设错误,则q2为空nonEmtpyQ = &obj->q1;//此时q1就为空}while (QueueSize(nonEmtpyQ) > 1){QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的队列数据导到空的队列,直到只剩一个QueuePop(nonEmtpyQ); //此时把非空的队头数据给删掉,方便后续导入数据}int top = QueueFront(nonEmtpyQ); //记录此时的栈顶数据QueuePop(nonEmtpyQ); //删除栈顶数据,使该队列置空return top;
}int myStackTop(MyStack* obj) {assert(obj);if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);//如果q1不为空,返回}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {assert(obj);//两个队列均为空,则为空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {assert(obj);QueueDestory(&obj->q1); //释放q1QueueDestory(&obj->q2); //释放q2free(obj);
}

3、用栈实现队列

  • 链接直达:

用栈实现队列

  • 题目:

  •  思路:

假设入栈的顺序为1 2 3 4,那么根据题意,想要达到1 2 3 4的出栈顺序以此实现队列。

此题和上一道题正好相反,用栈实现队列,上一道题中,我们需要把数据来回导,从而实现栈的后进先出功能,但是此题就完全不需要来回导了,只需要导一次即可。

假设我们有两个栈,分别命名为pushST和popST。并往栈pushST里头入4个数据1 2 3 4,在出数据时根据栈的性质只能拿到4,此时我们直接把4拿下来并导入栈popST里头,并继续把pushST栈里的数据导下来,直至栈pushST数据为空。此时popST数据即为  4 3 2 1,刚好反过来了。

根据队列的先进先出规则,进1 2 3 4,出必然是1 2 3 4,而上文已经知晓栈popST的数据为4 3 2 1,当删除数据时,会按照1 2 3 4 的顺序逐个删除。恰好利用栈的性质实现了队列的先进先出功能。并只需导一次即可,无需多次。

  •  代码如下:
//创建栈结构
typedef int STDataType;
typedef struct Stack
{STDataType* a; //存储数据int top; //栈顶的位置int capacity; //容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
//有效元素个数
int StackSize(ST* ps);//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//如果栈满了,考虑扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; //检测容量ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newcapacity; //更新容量}ps->a[ps->top] = x;//将数据压进去ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0; //如果top为0,那么就为真,即返回
}
//访问栈顶数据
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
//有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}/************创建好栈结构,开始正文************/
typedef struct {ST pushST; //插入数据的栈ST popST; //删除数据的栈
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申请队列类型assert(obj);StackInit(&obj->pushST);//初始化pushSTStackInit(&obj->popST);//初始化popSTreturn obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);StackPush(&obj->pushST, x);//不管有没有数据,都插入
}int myQueuePop(MyQueue* obj) {assert(obj);if (StackEmpty(&obj->popST)) //如果popST数据为空,要从pushST里导入数据才能删除{while (!StackEmpty(&obj->pushST)) //pushST数据不为空,就一直向popST里导入数据{StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉,方便后续继续导}}int front = StackTop(&obj->popST); //记录popST栈顶元素StackPop(&obj->popST);//删除popST栈顶元素,实现队列先进先出return front; //返回栈顶数据
}//取队头数据
int myQueuePeek(MyQueue* obj) {assert(obj);//如果popST数据为空,要从pushST里导入数据才能取到队头数据if (StackEmpty(&obj->popST)){while (!StackEmpty(&obj->pushST)) //pushST数据不为空,就一直向popST里导入数据{StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉,方便后续继续导}}return StackTop(&obj->popST);//直接返回栈顶元素
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}void myQueueFree(MyQueue* obj) {assert(obj);StackDestory(&obj->pushST);StackDestory(&obj->popST);free(obj);
}

4、设计循环队列

  • 链接直达:

设计循环队列

  • 题目:

  •  思路:

此题可以用数组实现,也可以用链表实现,但其实是用数组更加方便些。

数组:

假设队头front和队尾tail都指向第一个数据,在队尾插入数据,tail随着数据的插入跟着移动,tail始终为最后一个数据的下一个位置。删除数据只需要将队头front往后挪即可,不需要按照之前队列的pop一样删完还挪动数据,因为是循环链表,且数据是可以重复利用的。

这样分析下来再加上画图看似没有什么缺陷,但是存在两个问题?

  1. 什么情况下数组为空?
  2. 什么情况下数组满了?

问题1:

当tail = front时数组为空,看似没什么问题,但相等又要分两种情况。先画个图:

 由上图得知,在情况一下,数组里确实是一个数据也没有,并且tail也是等于front的,满足数组为空的条件,但是在情况二下,数组的数据全满,此时的tail和front同样是相等的,这里数组不为空了,而是全满,由此可见,是存在问题的。

解决方案:

这里我们可以多开一个空间,不存放数据,只是用来分别数组为空或满。原理如下:当数组长度为4时,也就是说实际能存放3个有效数据,另外一个空间用来判断空或满,此时判断空或满的条件如下:

  1. front == tail 时是空
  2. tail 下一个位置是 front 时,就是满

  •  代码如下:
typedef struct {int* a; //用数组模拟环形队列int front;//队头int tail; //队尾int k; //表示存的数据长度为k
} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj); //前置声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置声明MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建环形链表结构assert(obj);obj->a = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间,便于后续区分空或满obj->front = obj->tail = 0;obj->k = k; //队列存储有效数据长度为kreturn obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false; //队列已满,不能插入数据}obj->a[obj->tail] = value; //赋值if (obj->tail == obj->k){obj->tail = 0; //当tail走到尾端}else{obj->tail++;}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false; //队列为空,不能删除}if (obj->front == obj->k){obj->front = 0; //当front走到尾端}else{obj->front++;}return true;
}
//取头
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1; //队列为空,取不了}return obj->a[obj->front]; //返回队头
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1; //队列为空,取不了}if (obj->tail == 0){return obj->a[obj->k]; //tail为0,队尾在长度的最后一个位置}else{return obj->a[obj->tail - 1];}
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail; //front==tail时为空
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if (obj->tail == obj->k && obj->front == 0){return true; //当tail尾端,front在头端时也是满}else{return obj->tail + 1 == obj->front; //一般情况,当tail的下一个位置为front时为满}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

http://chatgpt.dhexx.cn/article/fUnYRbOw.shtml

相关文章

栈stack和队列

栈和队列 一 栈和队列二 栈三.队列 一 栈和队列 栈和队列是两种重要的线性结构。从数据结构来看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集(也具有顺序结构和链式结构),它们是操作受限的…

链表,队列和栈的区别

链表,队列和栈都是数据结构的一种。Sartaj Sahni 在他的《数据结构、算法与应用》一书中称:“数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象&#x…

栈与队列的定义与区别

1、栈 首先,普通的线性表实现是有两个端口可以访问的,但是如果作为栈就要封闭一端,只能访问另一端。这当然不是自讨苦吃,栈是一种抽象数据结构,是对现实世界对象的模拟。比如,自助餐厅中的一叠盘子&#x…

java 队列和栈的区别

栈和队列的区别 (1)数据插入删除 栈是一种特殊的线性表,他只能在一段进行插入和删除操作,就好像是一个井一样。进行数据插入和删除就类似于井口,称为栈定。而井也是有底部的,栈无法进行插入删除操作的这一…

监督学习和无监督学习的区别(机器学习)

机器学习主要分为两类 监督学习无监督学习 两者的区别主要是是否需要人工参与数据结果的标注 监督学习:教计算机如何去完成预测任务(有反馈),预先给一定数据量的输入和对应的结果即训练集,建模拟合,最后让…

简单说下有监督学习和无监督学习的区别

简单说下有监督学习和无监督学习的区别 解析: 有监督学习:对具有标记的训练样本进行学习,以尽可能对训练样本集外的数据进行分类预测。(LR,SVM,BP,RF,GBDT) 无监督学习:对未标记的样本进行训练学习&#xf…

一个简单的例子来理解监督学习和非监督学习及其区别

首先,必须理解两个基本概念:特征值和目标值,先看图例 1、特征值: 特征值是指数据的特征,对于每个样本,通常具有一些 "属性"(Attribute)或者说 ”特征“(Featu…

监督学习、无监督学习和半监督学习区别

1、概念 1.1监督学习(数据集有输入和输出数据):通过已有的一部分输入数据与输出数据之间的相应关系。生成一个函数,将输入映射到合适的输出,比如分类。 1.2无监督学习(数据集中只有输入)&…

监督、自监督、半监督、无监督学习的区别

目录 一、简易版区别 二、详细版区别 一、简易版区别 A Survey on Semi-, Self-and Unsupervised Learning for Image Classification 文中的解释: 监督学习(a):给出全部样本红蓝两类的标签 半监督学习(b&#xf…

有监督学习与无监督学习

机器学习的常用方法,主要分为有监督学习(supervised learning)和无监督学习(unsupervised learning)。简单的归纳就是,是否有监督(supervised),就看输入数据是否有标签(label)。输入数据有标签&…

有监督和无监督

来自有监督vs.无监督,傻傻分不清楚? - 搜狐网 网上对于有监督和无监督差异性的文章非常多,本文将重点从应用的角度来阐述如何选择有监督和无监督。 对比一:有标签 vs. 无标签 有监督又被称为“有老师的学习”,无监督被…

机器学习:有监督和无监督之间有什么区别

机器学习是人工智能的一个子集,它通过示例和经验教会计算机执行任务,是研究和开发的热门领域。我们每天使用的许多应用程序都使用机器学习算法,包括AI助手,Web搜索和机器翻译。 您的社交媒体新闻提要由机器学习算法提供支持。您、…

有监督学习与无监督学习的几大区别

当下无监督作为一种热门的机器学习技术,网上有不少关于无监督与有监督差异讨论的文章。DataVisor作为率先将无监督技术运用在反欺诈行业的娇娇领先者,我们在本文中,将深入浅出的讲解无监督机器学习技术与有监督技术在不同方面的区别&#xff…

监督学习和无监督学习区别

前言 机器学习分为:监督学习,无监督学习,半监督学习(也可以用hinton所说的强化学习)等。 在这里,主要理解一下监督学习和无监督学习。 监督学习(supervised learning) 从给定的训…

关于使用burpsuite时,“安全连接失败,使用了无效的证书”问题【已解决】

安装好burpsuite,配置好网络连接代理后,导入了证书,访问某一网站还是会出现如下现象: 解决方案: 打开浏览器设置-高级-证书-证书机构,删除刚才导入的证书。 再次访问http:\burp下载证书。 再次在设置-高级…

火狐浏览器出现“建立安全连接失败”PR_CONNECT_RESET_ERROR解决方法

访问一个网站出现这样的问题,可能是因为自己设置一些东西导致DNS解析出错。 我找了网上几个比较主流的方法都不能解决,最后就是一招刷新DNS解决了。(哭笑不得) 解决方法: 按“win R”键,启动运行窗口&a…

Horizon client连接错面报错:无法建立安全加密链路连接

一、问题描述 前方人员反馈在Horizon环境中交付桌面前,验证过程中,使用Horizon client登录错误报:无法建立安全加密链路连接,如下图所示: UAG软件版本:3.9 二、分析处理 1、检查客户端SSL配置选项&…

华为设备web登录,安全连接失败问题解决办法

web登录华为交换机、路由器失败 详细错误信息如下: 解决办法 1、可以更换浏览器解决 2、火狐浏览器可以通过加载插件解决,插件链接点击打开链接 3、如果上面链接有问题按如下方法安装插件:1)附件组件-扩展-搜索Disable DHE 安…

selenium自动化学习--解决firefox无法建立安全连接的问题(TLS1.0/TLS1.1)

解决Firefoxselenium无法建立安全连接的问题SSL_ERROR_UNSUPPORTED_VERSION 问题:解决方案: 问题: 在使用pythonselenium做firefox浏览器自动化测试的时候,遇到了如下问题: 代码如下: profile webdriver.…