面试题：C语言实现动态扩展堆栈及异常处理

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

// 定义堆栈结构体
typedef struct Stack {
    int *data;
    int top;
    int capacity;
} Stack;

// 创建新堆栈
Stack* createStack(int initialCapacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(initialCapacity * sizeof(int));
    stack->top = -1;
    stack->capacity = initialCapacity;
    return stack;
}

// 检查堆栈是否已满
bool isFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 检查堆栈是否为空
bool isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 扩展堆栈
void expandStack(Stack *stack) {
    stack->capacity *= 2;
    stack->data = (int*)realloc(stack->data, stack->capacity * sizeof(int));
}

// 入栈操作
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        expandStack(stack);
    }
    stack->data[++stack->top] = value;
}

// 出栈操作
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        fprintf(stderr, "Stack is empty. Cannot pop.\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top--];
}

// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        fprintf(stderr, "Stack is empty. Cannot peek.\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top];
}

// 释放堆栈内存
void freeStack(Stack *stack) {
    free(stack->data);
    free(stack);
}

动态扩展策略

采用倍增策略，当堆栈已满时，将堆栈的容量翻倍。这种策略的好处是每次扩展时不需要频繁地重新分配内存，减少了内存分配和释放的开销。

时间复杂度分析

入栈操作：平均情况下，入栈操作的时间复杂度为O(1)。因为大部分情况下入栈直接在数组末尾添加元素，时间复杂度为O(1)。只有在堆栈满时需要扩展，扩展操作的时间复杂度为O(n)，但由于扩展是偶尔发生，采用摊还分析，平均时间复杂度仍为O(1)。
出栈操作：出栈操作只需要将栈顶指针减1，时间复杂度为O(1)。

空间复杂度分析

空间复杂度为O(n)，其中n为堆栈中元素的数量。在最坏情况下，由于采用倍增策略，堆栈的容量可能会达到2n，因此空间复杂度仍为O(n)。

异常处理机制设计

入栈异常处理：在入栈操作前，先检查堆栈是否已满。如果已满，调用expandStack函数进行扩展，从而避免入栈时空间不足的异常。
出栈异常处理：在出栈操作前，先检查堆栈是否为空。如果为空，通过fprintf输出错误信息，并调用exit函数终止程序，保证程序不会因为访问空堆栈而出错，从而保证程序的健壮性。

星途面试题库

面试题：C语言实现动态扩展堆栈及异常处理

知识考点

面试题答案

动态扩展策略

时间复杂度分析

空间复杂度分析

异常处理机制设计