我想知道利用栈，队列，串这种线性表分配的内存空间

Question

我想知道利用栈，队列，串这种线性表分配的内存空间是不是静态里的一片片栈帧这种空间，如果是，那栈帧是先进先出的，这和队列的先进后出是不是矛盾了，xiao白不懂请大lao指点一二

Answer 1

在 C 语言中，利用栈、队列和串这些线性表的内存空间一般是通过动态分配内存来实现的，而不是静态分配。

对于栈，可以使用 C 语言提供的标准库函数 malloc 和 free 来动态分配和释放堆内存。例如，我们可以定义一个结构体来表示栈：

typedef struct {
    int *data;      // 存储数据的数组
    int top;        // 栈顶指针
    int capacity;   // 栈的容量
} Stack;

Stack *create_stack(int capacity) {
    Stack *stack = (Stack *) malloc(sizeof(Stack));
    stack->data = (int *) malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

void push(Stack *stack, int value) {
    if (stack->top == stack->capacity - 1) {
        printf("Stack is full\n");
        return;
    }
    stack->data[++stack->top] = value;
}

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->data[stack->top--];
}

void destroy_stack(Stack *stack) {
    free(stack->data);
    free(stack);
}

在上面的代码中，我们首先定义了一个 Stack 结构体，其中包含一个指向存储数据的数组、一个指向栈顶元素的指针 top 和一个表示栈容量的整数 capacity。然后，我们使用 create_stack 函数来创建一个容量为 capacity 的栈，并使用 push、pop 和 destroy_stack 函数来向栈中压入数据、弹出数据和销毁栈。注意，在这里，栈使用的是数组实现，因此栈帧并没有直接涉及到。

对于队列和串，同样可以使用动态分配内存的方式来实现。例如，我们可以使用链式存储结构来实现队列和串，即通过指针将多个节点串联起来。

总之，在 C 语言中，栈、队列和串这些线性表的内存空间分配方式是动态分配的，而不是静态分配的。虽然栈帧在函数调用中也会被使用到，但它们与这些线性表的内存空间分配方式并没有直接关系。