当前位置：首页 > news >正文

【数据结构】栈与队列面试题（C语言）

news 来源：原创 2024/5/11 1:02:59

我们再用C语言做题时，是比较不方便的，因此我们在用到数据结构中的某些时只能手搓或者Ctrl+cv

我们这里用到的栈或队列来自栈与队列的实现

有效的括号

有效的括号，链接奉上。
在这里插入图片描述

解题思路：

先说结论：
因为我们是在讲栈与队列的面试题，故当然此题用栈或者队列做最为合适
但是为什么会想到使用栈与队列呢？
这就要求我们对数据结构具有比较高的熟悉度，看到题目就会想出比较恰当的应对措施，这与我们的做题程度也密不可分

利用栈的特性，当有左括号出现时，需要压栈，有右括号出现时pop出左括号进行匹配
在这里插入图片描述
解决完最主要的问题就可以逐步探测一些比较不容易被发现的坑点
，我会在代码实现中一步一步带大家深入

代码实现：

bool isValid(char* s) 
{Stack st;StackInit(&st);while(*s){if(*s == '{' || *s == '[' || *s == '('){StackPush(&st, *s);}else{char tmp = StackTop(&st);StackPop(&st);if(!(*s == '}' && tmp == '{'|| *s == ']' && tmp == '['|| *s == ')' && tmp == '(')){StackDestroy(&st);return false;}}s++;}StackDestroy(&st);return true;
}

写完之后我们提交，发现：在这里插入图片描述
这就说明我们应当在加一个判断，当栈中有剩余时，说明数量不匹配

    if(StackSize(&st) > 0){StackDestroy(&st);return false;}

继续提交，发现当只有一个右括号时，因为会top，而栈用又没有元素，所以报错，我们继续加一个判断
在这里插入图片描述
加的位置在while中的else

            if(StackSize(&st) == 0){StackDestroy(&st);return false;}

完整代码：

bool isValid(char* s) 
{Stack st;StackInit(&st);while(*s){if(*s == '{' || *s == '[' || *s == '('){StackPush(&st, *s);}else{if(StackSize(&st) == 0){StackDestroy(&st);return false;}char tmp = StackTop(&st);StackPop(&st);if(!(*s == '}' && tmp == '{'|| *s == ']' && tmp == '['|| *s == ')' && tmp == '(')){StackDestroy(&st);return false;}}s++;}if(StackSize(&st) > 0){StackDestroy(&st);return false;}StackDestroy(&st);return true;
}

用队列实现栈

在这里插入图片描述
用队列实现栈，链接奉上

解题思路：

在这里插入图片描述

代码实现：

typedef struct 
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() 
{MyStack* head = (MyStack*)malloc(sizeof(MyStack));QueueInit(&head->q1);QueueInit(&head->q2);return head;
}void myStackPush(MyStack* obj, int x) 
{Queue empty = obj->q1;if(!QueueEmpty(&empty))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 tmp = QueueFront(nonemptyq);QueuePop(nonemptyq);return tmp;
}int myStackTop(MyStack* obj) {Queue* emptyq = &obj->q1;Queue* nonemptyq = &obj->q2;if(!QueueEmpty(emptyq)){emptyq = &obj->q2;nonemptyq = &obj->q1;}return QueueBack(nonemptyq);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

用栈实现队列

在这里插入图片描述

用栈实现队列

解题思路：

与上一题类似，可以将两个栈来回导，最终实现

代码实现：

typedef struct {Stack s1;Stack s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&ret->s1);StackInit(&ret->s2);return ret;
}void myQueuePush(MyQueue* obj, int x) {if(!(StackEmpty(&obj->s1))){StackPush(&obj->s2, x);}else{StackPush(&obj->s1, x);}
}int myQueuePop(MyQueue* obj) {MyQueue* emptys = &obj->s1; MyQueue* nonemptys = &obj->s2; if(!StackEmpty(&obj->s1)){emptys = &obj->s2; nonemptys = &obj->s1; }while(StackSize(nonemptys) > 1){StackPush(emptys, StackTop(nonemptys));StackPop(nonemptys);}int ret = StackTop(nonemptys);StackPop(nonemptys);while(StackSize(emptys)){StackPush(nonemptys, StackTop(emptys));StackPop(emptys);}return ret;
}int myQueuePeek(MyQueue* obj) {MyQueue* emptys = &obj->s1; MyQueue* nonemptys = &obj->s2; if(!StackEmpty(&obj->s1)){emptys = &obj->s2; nonemptys = &obj->s1; }while(StackSize(nonemptys) > 1){StackPush(emptys, StackTop(nonemptys));StackPop(nonemptys);}int ret = StackTop(nonemptys);StackPush(emptys, StackTop(nonemptys));StackPop(nonemptys);while(StackSize(emptys)){StackPush(nonemptys, StackTop(emptys));StackPop(emptys);}return ret;
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->s1);StackDestroy(&obj->s1);free(obj);
}