c - 不使用指针的堆栈实现

Question

我需要实现一个非常基本的堆栈数据结构，以便在不使用指针的情况下在 C 中保存整数。这可能只使用数组吗？简单的伪代码将不胜感激。

编辑:我正在使用一个名为 UPPAAL 的模型检查工具支持 C 的基本功能，我需要使用 UPPAAL 不支持的递归函数。我考虑过使用我自己的堆栈实现递归，因为 UPPAAL 不支持指针。有更好的想法吗？

Answer 1

假设您被允许为整个结构进行一次动态分配(您必须以某种方式)，您可以只使用整数作为偏移量:

unsigned int capacity = 100;
unsigned int top      = 0;

int * buf = malloc(sizeof(int) * capacity);

// push:
buf[top++] = n;

// pop:
int value = buf[--top];

// empty:
int is_empty = (top == 0);

// increase capacity:
if (top == capacity)
{
    int * tmp = realloc(buf, capacity * 2 * sizeof(int));
    if (!tmp) { /* out of memory, die */ }
    buf = tmp;
    capacity *= 2;
}

// destroy
free(buf);

这段代码只是为了说明；在您的实现中，您显然会检查溢出和下溢。