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);

此代码仅用于说明；在您的实现中，您显然会检查溢出和下溢。