前情提要
本章节是数据结构的栈和队列的相关面试题目讲解~
以下的内容一定会让你对栈和队列相关知识的题目,有一个颠覆性的认识哦！！！
❗以下内容以C语言的方式实现❗
以下内容干货满满，跟上步伐吧~
👉前情提要
本次题目涉及面试题解答思路 &中等难度题目
欢迎大家上手测试一波🥰
📒面试真题【全面深度解析】
🏷️ 有效的括号【难度：简单】
:mag:题目传送门：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合
💡解题关键：
➡️思路： 栈
❓为什么利用栈这个结构呢
1️⃣括号一左一右的特性，刚好符合栈的LIFO（Last in first out）原则
2️⃣那这样我们就可以利用栈将左括号类型的括号依次入栈，根据括号需要相互对应的特性，就可以按顺序出栈并依次按顺序与右括号类型比较，看是否匹配
若直至左括号类型全部出栈，且全都匹配的话，说明括号全部匹配，返回true
否则，若中途有不匹配的，则匹配失败，返回false
❗特别注意：
🔥特殊情况：
数组没走完，但栈却是NULL的【Eg：第一个元素就为右括号类型】，就可以不用接着匹配下去了，返回false
数组走完了，但栈却不为NULL，那此时相当于还有左括号类型没有得匹配，返回false
✊动图示例：
👉实现：
1️⃣实现栈
typedef char STDatatype;typedef struct Stack{ STDatatype* a; int top; // 栈顶 int capacity;}ST; void StackInit(ST* ps);void StackDestroy(ST* ps);void StackPush(ST* ps, STDatatype x);void StackPop(ST* ps);bool StackEmpty(ST* ps);int StackSize(ST* ps);STDatatype StackTop(ST* ps); void StackInit(ST* ps){ assert(ps); ps->a = NULL; ps->top = 0; // -1 ps->capacity = 0;} void StackDestroy(ST* ps){ assert(ps); if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacity = 0;} void StackPush(ST* ps, STDatatype x){ assert(ps); // 检查空间够不够，不够就增容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDatatype* tmp = realloc(ps->a, sizeof(STDatatype)*newcapacity); if (tmp == NULL) { printf("rellaoc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++;} void StackPop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); --ps->top;} bool StackEmpty(ST* ps){ assert(ps); return ps->top == 0;} int StackSize(ST* ps){ assert(ps); return ps->top;} STDatatype StackTop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1];}
复制代码
2️⃣实现括号匹配功能
bool isValid(char * s){ ST st; StackInit(&st); bool match = true; while(*s) { if(*s == '[' || *s == '(' || *s == '{') { StackPush(&st, *s); s++; } else { //数组还没走完， //但栈已经空了 if(StackEmpty(&st)) { match = false; break; } char ch = StackTop(&st); StackPop(&st); if((*s == ']' && ch != '[') || (*s == '}' && ch != '{') || (*s == ')' && ch != '(')) { match = false; break; } else { s++; } } } //双重保险，预防上述第二种特殊情况 if(match == true) { match = StackEmpty(&st); } StackDestroy(&st); return match;}
复制代码
🏷️ 用队列实现栈【难度：简单】
:mag:题目传送门：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
实现 MyStack 类：
示例 1：
输入：["MyStack", "push", "push", "top", "pop", "empty"][[], [1], [2], [], [], []]输出：[null, null, null, 2, 2, false]
解释：MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False
复制代码
💡解题关键：
➡️思路： 本质由队列底层实现栈
1️⃣实现pop接口
两个队列实现pop（出栈）接口，即实现后进先出，但队列的性质是先进先出，刚好相反，我们要怎么实现呢？
此时就刚好体现两个队列的作用了，将两个队列分为空队列、 非空队列【非空 or 空是依据队列是否为空来灵活定义的，随时变化的】
将 不为空的队列 的数据出队列入到 空队列 当中，当非空队列只剩下一个元素时，就可以pop，达到LIFO的目的
❗这里很巧妙的利用特性即达到后进后出，也达到即使元素在队列间不断出入，也没有改变在栈的角度看这些元素之间的顺序发生改变
✊动图示例：
✊动图示例：
👉实现：
1️⃣实现队列的数据结构
typedef int QDataType;typedef struct QueueNode{ struct QueueNode* next; QDataType data; }QNode;
typedef struct Queue{ //int size; QNode* head; QNode* tail;}Queue;
void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq, QDataType x);void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);int QueueSize(Queue* pq);
void QueueInit(Queue* pq){ assert(pq); pq->head = pq->tail = NULL;}
void QueueDestroy(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)); if (newnode == NULL) { printf("malloc fail\n"); 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; }}
void QueuePop(Queue* 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; }}
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;}
bool QueueEmpty(Queue* pq){ assert(pq); return pq->head == NULL;}
int QueueSize(Queue* pq){ assert(pq); QNode* cur = pq->head; int size = 0; while (cur) { ++size; cur = cur->next; }
return size;}
复制代码
2️⃣模拟实现栈的接口
typedef struct { Queue q1; Queue q2; } MyStack; //初始化“栈”MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst;} //pushvoid myStackPush(MyStack* obj, int x) { //给非空队列进行入队操作 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); }} //popint myStackPop(MyStack* obj) {
Queue* pEmpty = &obj->q1, *pNonEmpty = &obj->q2; if(!QueueEmpty(&obj->q1)) { pEmpty = &obj->q2; pNonEmpty = &obj->q1; } while(QueueSize(pNonEmpty) > 1) { QueuePush(pEmpty, QueueFront(pNonEmpty)); QueuePop(pNonEmpty); } int top = QueueFront(pNonEmpty); //队尾元素出队 QueuePop(pNonEmpty); return top;} //topint myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); }} //emptybool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);} //释放void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj);}
复制代码
🏷️用栈实现队列【难度：简单】
:mag:题目传送门：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
示例 1：
输入：["MyQueue", "push", "push", "peek", "pop", "empty"][[], [1], [2], [], [], []]输出：[null, null, null, 1, 1, false]
解释：MyQueue myQueue = new MyQueue();myQueue.push(1); // queue is: [1]myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)myQueue.peek(); // return 1myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false
复制代码
💡解题关键：
➡️思路： 本质由栈的底层实现队列
1️⃣实现pop接口
两个栈实现pop（出队列）接口，即实现先进先出，但栈的性质是后进先出，刚好相反，我们要怎么实现呢？
此时就刚好体现两个栈的作用了，将两个队列分为专门入数据的栈、 专门出数据的栈
将 专门入数据的栈 的数据出栈入到 专门出数据的栈 ，但正因为栈是后进先出的特性，导致数据入到另外一个栈里的顺序就是逆转过后的【不同于队列实现栈】，那此时就可以按照栈的特性去pop，达到队列的LIFO的目的
这也是为什么令一个栈为专门入数据的栈，另外一个栈为专门出数据的栈
❗这里很巧妙的利用特性即达到先进后出，正是因为数据从一个栈里出来再入到另外一个栈里的顺序发生改变，从而可以直接利用后进先出达到先进先出的效果
✊动图示例：
✨综上：
我们只要每次想出队列的时候，直接看专门出数据的栈进行出数据即可，所以我们可以先判断专门出数据的栈是否为NULL
若为NULL，则将专门入数据的栈里的数据入到专门出数据的栈里，再由专门出数据的栈进行pop
若不为NULL，则可以直接在专门出数据的栈利用后进先出栈的特性，达到队列先进先出对于原本数据的出队列的顺序要求
2️⃣实现push接口
为了可以依旧保持“队列”内的元素的顺序不变，我们选择往专门如数据的栈里插入数据，就可以实现顺序不变的效果
✊动图示例：
👉实现：
1️⃣实现栈的数据结构
typedef int STDataType;
//数组实现栈typedef struct Stack{ STDataType* a; int capacity; //容量，方便增容 int top; // 表示栈顶}Stack;
//初始化void StackInit(Stack* pst);
//销毁void StackDestory(Stack* pst);
//插入void StackPush(Stack* pst, STDataType x);
//删除void StackPop(Stack* pst);
//取栈顶的数据【返回栈顶的数据】STDataType StackTop(Stack* pst);
//判断栈内是否为空bool StackEmpty(Stack* pst);
//返回栈内数据的个数int StackSize(Stack* pst);
void StackInit(Stack* pst){ assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); pst->top = 0; pst->capacity = 4;}
//销毁void StackDestory(Stack* pst){ assert(pst); free(pst->a); pst->a = NULL;
pst->capacity = pst->top = 0;}
//插入数据void StackPush(Stack* pst, STDataType x){ assert(pst);
if (pst->top == pst->capacity) { //增容 STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1);//结束程序 //这个-1不是return，而是给进程的，直接结束整个程序（return是结束当前函数） }
pst->a = tmp; pst->capacity = pst->capacity * 2; }
pst->a[pst->top] = x; pst->top++;}
//尾删【实际 就是删除排在最后，最晚插进来的 栈顶】void StackPop(Stack* pst){ //跟之前一样，对栈顶的数据进行删除时 //没必要抹除这个数据，只需要不访问到它就行 assert(pst); //这里唯一需要考虑的是：这个栈里面是不是空的 assert(!StackEmpty(pst)); //判断是不是 非空的 pst->top--;}
//返回栈顶的数据STDataType StackTop(Stack*pst){ assert(pst); //需要判断是不是不为空的 assert(!StackEmpty(pst));
return pst->a[pst->top - 1];}
//判断栈内是否为空bool StackEmpty(Stack* pst){ assert(pst); return pst->top == 0; //如果等于0，则说明为真，即 如果为空，就返回TURE //不为0，不为空，则返回 FALSE}
//返回栈内数据的个数int StackSize(Stack* pst){ assert(pst);
return pst->top; //top就是大小}
复制代码
2️⃣模拟实现队列的接口
typedef struct { Stack pushST; Stack popST;} MyQueue;
//初始化MyQueue* myQueueCreate(){ MyQueue*q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushST); StackInit(&q->popST);
return q;}
//插入void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x);}
//出队列int myQueuePop(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int top = StackTop(&obj->popST); StackPop(&obj->popST); return top;}
//获取对头的数据int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } }
return StackTop(&obj->popST);}
//emptybool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);}
//释放void myQueueFree(MyQueue* obj) { StackDestory(&obj->pushST); StackDestory(&obj->popST); free(obj);}
复制代码
🏷️ 设计循环队列【难度：中等】
:mag:题目传送门：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k
Front: 从队首获取元素。如果队列为空，返回 -1
Rear: 获取队尾元素。如果队列为空，返回 -1
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真
isEmpty(): 检查循环队列是否为空
isFull(): 检查循环队列是否已满
💡解题关键：
➡️思路： 用数组实现循环队列
1️⃣ 当我们创造的空间大小与所需空间大小相等时，我们便无法再借助头尾指针去表示循环队列什么时候为NIULL，什么时候空间满了
所以此时我们便可以通过创造比实际需求多1个空间的循环队列给予头尾指针更多的操作空间
2️⃣判空条件即为：tail == front
3️⃣判断队列满的条件：【tail+1= tailNext】tailNext== front
4️⃣push的时候就根据tail走的去入数据
5️⃣pop的时候就用front去走一步以达到删除一个元素的目的，因为front表示的队头的下标，如果队头下标移动了，说明判空条件也随着front下标的移动而移动，到时候原来的队头位置的数据就会因为入新的数据而被覆盖
❗特别注意：
✊动图示例：
👉实现：
typedef struct { int* a; int k;//记录队列实际个数的大小
int front; //头的下标 int tail; //本质：指向的是真正有数据的结点的下一个结点 //【因为tail指向的地方是没有数据的，而上一个是有数据的】} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->a = (int*)malloc(sizeof(int) * (k+1)); cq->front = 0; cq->tail = 0; cq->k = k; return cq;}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;}
bool myCircularQueueIsFull(MyCircularQueue* obj) { int tailNext = obj->tail+1; if(tailNext == obj->k+1) //说明此时tail已经到达空间的尾 { tailNext = 0;// 那此时next就为 队列的头 }
return tailNext == obj->front;}
//入数据bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){ if(myCircularQueueIsFull(obj)) { return false; } else { obj->a[obj->tail] = value;
obj->tail++;
//如果tail此时在尾巴上 if(obj->tail == obj->k+1) { obj->tail = 0; }
return true; }}
//出数据bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } else { obj->front++; if(obj->front == obj->k+1) { obj->front = 0; } return true; }}
//取头int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->front];}
//取尾 -- tail的前一个int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } //极端情况：tail = 0的时候 if(obj->tail == 0) { return obj->a[obj->k]; } return obj->a[obj->tail-1];}
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj);}
复制代码
🌟总结
综上，我们基本了解了数据结构中的"栈和队列重要面试真题"的知识啦~~
恭喜你的内功又双叒叕得到了提高！！！
感谢你们的阅读
后续还会继续更新，欢迎持续关注哟~
评论