【秋招】嵌入式面试八股文 - 数据结构 队列与栈篇

【秋招】嵌入式面试八股文 - 最全专栏

一、栈(Stack)基础

1. 基本概念

• 栈是一种遵循后进先出(LIFO, Last In First Out)原则的线性数据结构
• 只允许在一端(栈顶)进行插入和删除操作
• 基本操作：push(入栈)、pop(出栈)、peek/top(查看栈顶元素)

2. 栈的实现方式

数组实现

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶指针
} ArrayStack;

// 初始化栈
void initStack(ArrayStack* stack) {
    stack->top = -1;  // 栈空时top为-1
}

// 判断栈是否为空
bool isEmpty(ArrayStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
bool isFull(ArrayStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
bool push(ArrayStack* stack, int value) {
    if (isFull(stack)) {
        return false;  // 栈满，入栈失败
    }
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(ArrayStack* stack, int* value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，出栈失败
    }
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(ArrayStack* stack, int* value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，获取失败
    }
    *value = stack->data[stack->top];
    return true;
}

链表实现

typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct {
    StackNode* top;  // 栈顶指针
} LinkedStack;

// 初始化栈
void initStack(LinkedStack* stack) {
    stack->top = NULL;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->top == NULL;
}

// 入栈操作
void push(LinkedStack* stack, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，出栈失败
    }
    StackNode* temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，获取失败
    }
    *value = stack->top->data;
    return true;
}

二、队列(Queue)基础

1. 基本概念

• 队列是一种遵循先进先出(FIFO, First In First Out)原则的线性数据结构
• 只允许在一端(队尾)进行插入操作，在另一端(队头)进行删除操作
• 基本操作：enqueue(入队)、dequeue(出队)、peek/front(查看队头元素)

2. 队列的实现方式

数组实现(循环队列)

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
    int size;   // 当前队列大小
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* queue) {
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
}

// 判断队列是否为空
bool isEmpty(CircularQueue* queue) {
    return queue->size == 0;
}

// 判断队列是否已满
bool isFull(CircularQueue* queue) {
    return queue->size == MAX_SIZE;
}

// 入队操作
bool enqueue(CircularQueue* queue, int value) {
    if (isFull(queue)) {
        return false;  // 队列已满，入队失败
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;  // 循环队列
    queue->size++;
    return true;
}

// 出队操作
bool dequeue(CircularQueue* queue, int* value) {
    if (isEmpty(queue)) {
        return false;  // 队列为空，出队失败
    }
    *value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;  // 循环队列
    queue->size--;
    return true;
}

// 获取队头元素
bool peek(CircularQueue* queue, int* value) {
    if (isEmpty(queue)) {
        return false;  // 队列为空，获取失败
    }
    *value = queue->data[queue->front];
    return true;
}

链表实现

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;  // 队头指针
    QueueNode* rear;   // 队尾指针
} LinkedQueue;

// 初始化队列
void initQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
bool isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(LinkedQueue* queue, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
bool dequeue(LinkedQueue* queue, int* value) {
    if (isEmpty(queue)) {
        return false;  // 队列为空，出队失败
    }
    
    QueueNode* temp = queue->front;
    *value = temp->data;
    
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;  // 队列变为空
    }
    
    free(temp);
    return true;
}

// 获取队头元素
bool peek(LinkedQueue* queue, int* value) {
    if (isEmpty(queue)) {
        return false;  // 队列为空，获取失败
    }
    *value = queue->front->data;
    return true;
}

三、栈的经典面试题

1. 有效的括号匹配

问题：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

思路：使用栈来匹配括号，遇到左括号入栈，遇到右括号时与栈顶元素匹配。

bool isValid(char* s) {
    int len = strlen(s);
    if (len % 2 != 0) return false;  // 奇数长度一定不匹配
    
    char stack[len];
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            // 左括号入栈
            stack[++top] = s[i];
        } else {
            // 右括号，检查栈是否为空
            if (top == -1) return false;
            
            // 检查是否匹配
            if ((s[i] == ')' && stack[top] != '(') ||
                (s[i] == '}' && stack[top] != '{') ||
                (s[i] == ']' && stack[top] != '[')) {
                return false;
            }
            
            // 匹配成功，弹出栈顶元素
            top--;
        }
    }
    
    // 栈为空表示所有括号都匹配
    return top == -1;
}

2. 用栈实现队列

问题：使用栈实现队列的下列操作：push、pop、peek、empty。

思路：使用两个栈，一个用于入队(pushStack)，一个用于出队(popStack)。

typedef struct {
    int* pushStack;
    int pushTop;
    int* popStack;
    int popTop;
    int capacity;
} MyQueue;

// 创建队列
MyQueue* myQueueCreate(int capacity) {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->pushStack = (int*)malloc(sizeof(int) * capacity);
    queue->popStack = (int*)malloc(sizeof(int) * capacity);
    queue->pushTop = -1;
    queue->popTop = -1;
    queue->capacity = capacity;
    return queue;
}

// 将元素从pushStack移动到popStack
void transfer(MyQueue* queue) {
    if (queue->popTop == -1) {  // 只有当popStack为空时才转移
        while (queue->pushTop != -1) {
            queue->popStack[++queue->popTop] = queue->pushStack[queue->pushTop--];
        }
    }
}

// 入队操作
void myQueuePush(MyQueue* queue, int x) {
    queue->pushStack[++queue->pushTop] = x;
}

// 出队操作
int myQueuePop(MyQueue* queue) {
    transfer(queue);
    if (queue->popTop == -1) {
        return -1;  // 队列为空
    }
    return queue->popStack[queue->popTop--];
}

// 获取队头元素
int myQueuePeek(MyQueue* queue) {
    transfer(queue);
    if (queue->popTop == -1) {
        return -1;  // 队列为空
    }
    return queue->popStack[queue->popTop];
}

// 判断队列是否为空
bool myQueueEmpty(MyQueue* queue) {
    return (queue->pushTop == -1 && queue->popTop == -1);
}

// 释放队列
void myQueueFree(MyQueue* queue) {
    free(queue->pushStack);
    free(queue->popStack);
    free(queue