CODEWITHSUNDEEP
calgorithmdata-structures
Saba Ahang
Saba Ahang

Reputation: 598

Stack implementation without using pointers

I need to implement a very basic stack data structure for keeping integers in C without using pointers. Is this possible using only arrays? Simple pseudo code would be highly appreciated.

Edit: I'm using a model checking tool called UPPAAL that supports the basic functionalities of C and I need to use a recursive function which UPPAAL doesn't support. I thought about implementing the recursion using my own stack because UPPAAL doesn't support pointers. Any better ideas?

Upvotes: 0

Views: 2337

Answers (1)

Kerrek SB
Kerrek SB

Reputation: 476910

Assuming that you're allowed to make one dynamic allocation for the entire structure (which you must, one way or another), you can just use integers for an offset:

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

This code is just for exposition; in your implementation you would obviously check for overflow and underflow.

Upvotes: 3

Related Questions