面试题：C语言中堆栈的基本操作实现

Question

请用C语言实现一个简单的堆栈，要求包含入栈（push）、出栈（pop）、判断堆栈是否为空（is_empty）以及获取栈顶元素（peek）这几个基本操作的函数。假设堆栈存储的数据类型为整数。

Answer 1

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

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

// 创建一个新的栈
Stack* create_stack(int size) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(size * sizeof(int));
    stack->top = -1;
    stack->capacity = size;
    return stack;
}

// 判断栈是否为空
int is_empty(Stack *stack) {
    return stack->top == -1;
}

// 入栈操作
void push(Stack *stack, int value) {
    if (stack->top == stack->capacity - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 出栈操作
int pop(Stack *stack) {
    if (is_empty(stack)) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top--];
}

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

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

你可以使用以下方式调用这些函数：

int main() {
    Stack *stack = create_stack(5);
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);

    printf("Is stack empty? %s\n", is_empty(stack)? "Yes" : "No");
    printf("Top element: %d\n", peek(stack));
    printf("Popped element: %d\n", pop(stack));
    printf("Is stack empty? %s\n", is_empty(stack)? "Yes" : "No");

    free_stack(stack);
    return 0;
}