行业资讯

C语言栈与队列面试题实例分析

发布时间：2022-04-11 14:00:01 作者：iii
来源：亿速云 阅读：137

C语言栈与队列面试题实例分析

在C语言的面试中，栈（Stack）和队列（Queue）是常见的数据结构，面试官经常会通过它们来考察应聘者对基础数据结构的理解和应用能力。本文将通过几个典型的面试题实例，分析栈与队列的应用场景和解题思路。

1. 栈的应用：括号匹配

题目描述

给定一个只包含 (、)、{、}、[、] 的字符串，判断字符串中的括号是否匹配。

解题思路

括号匹配问题通常使用栈来解决。遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，检查栈顶元素是否与之匹配。如果匹配，则弹出栈顶元素；如果不匹配，则说明括号不匹配。最后，如果栈为空，则说明所有括号都匹配。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, char c) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++s->top] = c;
}

char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return '\0';
    }
    return s->data[s->top--];
}

bool isMatch(char left, char right) {
    return (left == '(' && right == ')') || 
           (left == '{' && right == '}') || 
           (left == '[' && right == ']');
}

bool isValid(char *s) {
    Stack stack;
    initStack(&stack);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(&stack, s[i]);
        } else {
            if (isEmpty(&stack) || !isMatch(pop(&stack), s[i])) {
                return false;
            }
        }
    }
    return isEmpty(&stack);
}

int main() {
    char str[] = "{[()]}";
    if (isValid(str)) {
        printf("Valid\n");
    } else {
        printf("Invalid\n");
    }
    return 0;
}

分析

2. 队列的应用：滑动窗口最大值

题目描述

给定一个数组和一个滑动窗口的大小，找出所有滑动窗口中的最大值。

解题思路

滑动窗口问题通常使用双端队列（Deque）来解决。我们维护一个双端队列，队列中存储的是数组元素的索引。在遍历数组时，我们确保队列中的元素始终是当前窗口中的最大值。具体步骤如下： 1. 移除队列中不在当前窗口范围内的元素。 2. 移除队列中所有小于当前元素的元素。 3. 将当前元素的索引加入队列。 4. 如果当前窗口已经形成，则将队列头部元素作为当前窗口的最大值。

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Deque;

void initDeque(Deque *dq) {
    dq->front = -1;
    dq->rear = -1;
}

bool isEmpty(Deque *dq) {
    return dq->front == -1;
}

bool isFull(Deque *dq) {
    return (dq->rear + 1) % MAX_SIZE == dq->front;
}

void pushBack(Deque *dq, int value) {
    if (isFull(dq)) {
        printf("Deque is full!\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else {
        dq->rear = (dq->rear + 1) % MAX_SIZE;
    }
    dq->data[dq->rear] = value;
}

void popFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty!\n");
        return;
    }
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->front = (dq->front + 1) % MAX_SIZE;
    }
}

void popBack(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty!\n");
        return;
    }
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    }
}

int front(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty!\n");
        return -1;
    }
    return dq->data[dq->front];
}

int back(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty!\n");
        return -1;
    }
    return dq->data[dq->rear];
}

void maxSlidingWindow(int* nums, int numsSize, int k, int* result, int* resultSize) {
    Deque dq;
    initDeque(&dq);
    *resultSize = 0;

    for (int i = 0; i < numsSize; i++) {
        while (!isEmpty(&dq) && front(&dq) < i - k + 1) {
            popFront(&dq);
        }
        while (!isEmpty(&dq) && nums[back(&dq)] < nums[i]) {
            popBack(&dq);
        }
        pushBack(&dq, i);
        if (i >= k - 1) {
            result[(*resultSize)++] = nums[front(&dq)];
        }
    }
}

int main() {
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 3;
    int result[MAX_SIZE];
    int resultSize;

    maxSlidingWindow(nums, numsSize, k, result, &resultSize);

    for (int i = 0; i < resultSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}

分析

3. 栈与队列的结合：用栈实现队列

题目描述

使用栈实现队列的以下操作： - push(x)：将元素 x 推入队列。 - pop()：移除并返回队列的头部元素。 - peek()：返回队列的头部元素。 - empty()：判断队列是否为空。

解题思路

使用两个栈来实现队列。一个栈用于入队操作，另一个栈用于出队操作。当需要出队时，如果出队栈为空，则将入队栈中的所有元素依次弹出并压入出队栈中，然后从出队栈中弹出元素。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top];
}

typedef struct {
    Stack inStack;
    Stack outStack;
} MyQueue;

void myQueueInit(MyQueue *q) {
    initStack(&q->inStack);
    initStack(&q->outStack);
}

void myQueuePush(MyQueue *q, int x) {
    push(&q->inStack, x);
}

int myQueuePop(MyQueue *q) {
    if (isEmpty(&q->outStack)) {
        while (!isEmpty(&q->inStack)) {
            push(&q->outStack, pop(&q->inStack));
        }
    }
    return pop(&q->outStack);
}

int myQueuePeek(MyQueue *q) {
    if (isEmpty(&q->outStack)) {
        while (!isEmpty(&q->inStack)) {
            push(&q->outStack, pop(&q->inStack));
        }
    }
    return peek(&q->outStack);
}

bool myQueueEmpty(MyQueue *q) {
    return isEmpty(&q->inStack) && isEmpty(&q->outStack);
}

int main() {
    MyQueue q;
    myQueueInit(&q);

    myQueuePush(&q, 1);
    myQueuePush(&q, 2);
    printf("%d\n", myQueuePeek(&q));  // 输出 1
    printf("%d\n", myQueuePop(&q));   // 输出 1
    printf("%d\n", myQueueEmpty(&q)); // 输出 0 (false)

    return 0;
}

分析

总结

栈和队列是C语言面试中常见的数据结构，掌握它们的基本操作和应用场景对于解决实际问题非常重要。通过以上几个实例的分析，我们可以看到栈和队列在解决括号匹配、滑动窗口最大值以及用栈实现队列等问题中的灵活应用。希望本文能帮助读者更好地理解和应用栈与队列。

推荐阅读：
  1. 如何使用JavaScript实现栈与队列
  2. Python面试题实例分析

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c语言

上一篇：MSSQL基本语法实例分析

下一篇：怎么使用SpringBoot配置多数据源

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号