Stack - C语言（LeetCode107）

前言

在实现LeetCode 107题时，发现它用到了栈、队列和树这三种数据结构，使用C++、Java或其它高级语言，这个题的实现就没有什么难度。C语言中没有栈和队列这样的数据结构，需要手动编写，不过，这也是一种锻炼。

分析

栈（Stack）的特性是先入后出，它的基本操作有：

#define SIZE       1000
#define INCREMENT  100
typedef struct {
    int* base;

    int base;
    int size;
} Stack;

// 基本操作
Stack* createStack(void);
Stack* createStackWithArray(int* arr, int size);
void destroyStack(Stack* stack);
bool extendStack(Stack* stack);
void pushStack(Stack* stack, int data);
int popStack(Stack* stack);
bool isStackEmpty(Stack* stack);
int sizeOfStack(Stack* stack);
int lengthOfStack(Stack* stack);
void traverseStack(Stack* stack);

实现

实现需要注意的是，在栈满的时候，即top >= size时，需要realloc内存，增大栈的长度。

Stack* createStack(void) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    
    if (!stack)
        return NULL;
    
    stack->base = (int*)malloc(sizeof(int) * SIZE);
    stack->top = 0;
    stack->size = SIZE;
    
    return stack;
}

Stack* createStackWithArray(int* arr, int size) {
    if (size == 0)
        return NULL;
    
    Stack* stack = createStack();
    
    for (int i = 0; i < size; ++i) {
        pushStack(stack, arr[i]);
    }
    
    return stack;
}

void destroyStack(Stack* stack) {
    free(stack->base);
    free(stack);
}

bool extendStack(Stack* stack) {
    int newSize = stack->size + INCREMENT;
    int* extendedBase = (int*)realloc(stack->base, sizeof(int) * newSize);
    
    if (!extendedBase)
        return false;
    
    stack->base = extendedBase;
    stack->size = newSize;
    
    return true;
}

void pushStack(Stack* stack, int data) {
    if (stack->top >= stack->size) {
        if (!extendStack(stack))
            return ;
    }
    
    stack->base[stack->top++] = data;
}

int popStack(Stack* stack) {
    if (stack->top == 0)
        return -1;
    
    return stack->base[--stack->top];
}

bool isStackEmpty(Stack* stack) {
    return stack->top == 0;
}

int sizeOfStack(Stack* stack) {
    return stack->size;
}

int lengthOfStack(Stack* stack) {
    return stack->top;
}

void traverseStack(Stack* stack) {
    if (stack->top == 0 || !stack)
        return ;
    
    printf("Traverse from Bottom to top: \n");
    for (int i = 0; i < stack->top; ++i) {
        printf("%d ", stack->base[i]);
    }
    
    printf("\n");
}