1、括号匹配问题
链接直达：
有效的括号
题目：
思路：
做题前，得先明确解题方案是啥，此题用栈的思想去解决是较为方便的，栈明确指出后进先出。我们可以这样设定：
- 遇到左括号“ ( ”、“ [ ”、“ { ”，入栈。
- 遇到右括号“ ) ”、“ ] ”、“ } ”，出栈，跟左括号进行匹配，不匹配就报错。
上两句话的意思就是说我去遍历字符串，如果遇到左括号，就入栈；遇到右括号，就出栈顶元素，并判断这个右括号是否与栈顶括号相匹配，若不匹配则返回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 failn"); 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、用队列实现栈
链接直达：
用队列实现栈
题目：
思路：
做题之前，再明确下两个基本知识点
- 栈：后进先出
- 队列：先进先出
此题要用先进先出的队列来实现后进先出的栈，并模拟实现队列的基本接口。
假设我们有一串数字，进入队列a顺序为1 2 3 4，此时再有一个队列b，此时我们取队列a的队头数据，并将其导入队列b，当队列a出到只剩最后一个时，把队列a给pop删掉，此时队列b就是1 2 3，间接性是实现了栈的功能，实现了后进先出的功能。当我们需要再入数据时，只需往不为空的队列入即可。再出就像刚刚那样。简而言之两句话：
- 入栈：push数据到不为空的队列。
- 出栈：把不为空的队列的数据前n-1导入另一个空队列，最后剩下一个删掉。
本质：保持一个队列存储数据，另外一个队列空着，要出栈时，空队列用来导数据。
代码如下：
//创建队列结构 typedef int qdatatype; //方便后续更改存储数据类型，c/c++开发分享C语言栈与队列面试题详解以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; //队列q1 queue q2; //队列q2 } mystack; mystack* mystackcreate() { mystack* pst = (mystack*)malloc(sizeof(mystack)); //申请一个mystack类型的栈 assert(pst); queueinit(&pst->q1);//初始化队列1 queueinit(&pst->q2);//初始化队列2 return 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); //释放q1 queuedestory(&obj->q2); //释放q2 free(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 failn"); 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);//初始化pushst stackinit(&obj->popst);//初始化popst return 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：
当tail = front时数组为空，看似没什么问题，但相等又要分两种情况。先画个图：
由上图得知，在情况一下，数组里确实是一个数据也没有，并且tail也是等于front的，满足数组为空的条件，但是在情况二下，数组的数据全满，此时的tail和front同样是相等的，这里数组不为空了，而是全满，由此可见，是存在问题的。
解决方案：
这里我们可以多开一个空间，不存放数据，只是用来分别数组为空或满。原理如下：当数组长度为4时，也就是说实际能存放3个有效数据，另外一个空间用来判断空或满，此时判断空或满的条件如下：
- front == tail 时是空
- 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; //队列存储有效数据长度为k return 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); }
到此这篇关于c语言栈与队列面试题详解的文章就介绍到这了,更多相关c语言 栈与队列内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！
需要了解更多c/c++开发分享C语言栈与队列面试题详解，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/1076781.html