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

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; } 

分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符只会被压入或弹出栈一次。
• 空间复杂度：O(n)，在最坏情况下，栈的大小与字符串长度相同。

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; } 

分析

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被压入和弹出队列一次。
• 空间复杂度：O(k)，队列的大小最多为窗口大小 k。

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; } 

分析

• 时间复杂度：push 操作的时间复杂度为 O(1)，pop 和 peek 操作的时间复杂度为 O(n)，但在摊还分析下，每个元素最多被压入和弹出两次，因此摊还时间复杂度为 O(1)。
• 空间复杂度：O(n)，其中 n 是队列中的元素数量。

总结

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