Simple stack of integers

Question

I've a simple push/pop implementation in my program:

void Push(int* stack, int top, int item)
{
  if (top == SIZE - 1) {
    printf("Overflow\n");
    return;
  } else if (item == INT_MIN) {
    printf("Item size out of bounds\n");
    return;
  }
  stack[++top] = item;
}

int Pop(int* stack, int top)
{
  if (top == -1) {
    printf("Empty\n");
    return INT_MIN;
  }
  return stack[top--];
}

In the Pop() function, I've wanted to return some kind of error code when the stack is empty but since all of the int values are valid returns: Can I resort to reserving INT_MIN for this? Is this a 'good practice', have unwanted consequences etc?

Answer 1

This is a classic example of in-band error signalling, and it's not a good idea (I think you suspect this, having asked about it). You need to separate the data from the error/success status of the function. There are several ways to do this, but most of them involve a return value for one, and a pointer argument for the other. For instance,

bool Push(int *stack, int *top, int item);
int Pop(const int *stack, int *top, bool *success);

Note that stack should be const, and this function will not work correctly unless top is passed by reference.

Also, for your error prints, you should usually print to stderr and not stdout.

Answer 2

Can I resort to reserving INT_MIN for this?

Yes.

Is this a 'good practice', have unwanted consequences etc?

Not good. This is a poor practice.

The obvious unwanted consequences is that code cannot handle all int.

It is good that Push(..., ..., INT_MIN) does fail, yet calling code does not receive an indication of a failure. Instead use the return value of the functions to indicate an error.

---

Missing

Missing code show how calling code should initialize its stack and top objects.

SIZE undefined.

Missing #include <limits.h>. (INT_MIN).

Missing #include <stdio.h>.

Unexpected output

Rather than print a overly simplistic message to stdout, return an error code and let the calling code decide what to do.

Answer 3

You’re Throwing Away the Top of the Stack

You increment or decrement your function parameter named top, but that’s just a local temporary variable inside the function. As soon as you return, any changes you make to it will be thrown away. Your code makes me extremely suspicious that you expect top to be passed by reference. But if you call pop(stack_top), the stack_top variable in the scope of the call will not be updated. In fact, you could even pass in a constant, like pop(0).

What you really want to do here is declare your stack as a struct with a member named top, and pass around pointers to that.

Your Stacks Cannot Have Different Sizes

There’s one predefined constant in your program, named SIZE, which must be the size of every stack in your program. This is an extremely inflexible approach and you should change it, but if you do want to stick with it, you could declare your stacks as int[SIZE] rather than int* and make it a little harder to shoot yourself in the foot.

You Could Widen the Return Type, But ....

There’s an even better approach here, but: Another way to handle error-signaling would be to make the return type wider than int. For example, you could store int32_t but return int64_t. Or, on most actually-existing implementations, sizeof(long long int) > sizeof(int)—but if you rely on this assumption, you ought to static_assert() it, which doesn’t cost you anything at runtime.

If you return a 64-bit value whose error code is something like LLONG_MIN, that’s equivalent to returning a 32-bit int in the lower word, and a 32-bit Boolean value in the upper word, but a lot more efficient than passing in two output parameters because they’re packed into a single value.

Are There Really Any Recoverable Errors?

There are only two possible error conditions: full and empty. You don’t actually have push() return any kind of error value as it is, only print a message to the console. These are already so exceptional that you’re breaking the behavior of the program to report the bug out-of-band. (Which, if you’re going to, should be to standard error instead of standard output.)

Trying to pop off an empty stack is a logic error in the program. It should never happen. If there ever is a case where client code is handed a stack that might or might not be empty, it would compare the size to 0 before calling pop(), not the return value afterward. It’s pretty silly to say that the program should handle this kind of logic error by passing in -1 as the size parameter and then testing the return value to check whether the value it passed in was -1! You could therefore justifiably make this a fatal logic error and abort the program with an error message.

If your stack uses dynamic memory, and allocates more as needed, it’s no longer possible to exceed the fixed size. You might get an out-of-memory error, but, first, you can handle that as an unrecoverable error too instead of returning an error value. Second, unless you’re coding some kind of embedded microcontroller or something, a modern OS would be thrashing to death long before it reported to an app that it was out of memory.

Use the Right Type for Size and Index Values

This is usually size_t. On most compilers, int is a 31-bit value, with a maximum value a little over 2 billion, less than the size of many modern data files. If you ever ported it to a 16-bit compiler, it could limit you to a size of only 32,767 elements on the stack.

Some programmers prefer to use a signed value, to check for wraparound. That would be ptrdiff_t, from <stddef.h>. (Your code does indeed use negative values of the stack top, but in a way you could easily refactor out.) A few shops, such as Microsoft, use an unsigned value whose top bit must be zero, like rsize_t.

Putting it All Together

Here’s a very bare-bones implementation that uses a vector:

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct stack_t {
  int* data;
  size_t used;
  size_t allocated;
} stack_t;

/* An expression suitable for:
 * stack_t foo = STACK_INITIALIZER;
 */
#define STACK_INITIALIZER { .data = NULL, .used = 0, .allocated = 0 }

int pop( stack_t* const stackp )
{
  // For this project, unrecoverable errors will be handled by assertions.
  assert(stackp->used > 0);

  return stackp->data[--stackp->used];
}

void push( stack_t* const stackp, const int value )
{
  if ( stackp->used == stackp->allocated ) {
    static const size_t default_alloc = 1024;
    stackp->allocated = (stackp->allocated == 0) ? default_alloc : stackp->allocated * 3 / 2;
    assert( stackp->allocated < SIZE_MAX / sizeof(int) );
    stackp->data = realloc( stackp->data, sizeof(int) * stackp->allocated );
    assert(stackp->data);
  }
  // If control reaches this point, stackp->data has enough storage to hold the new element.
  stackp->data[stackp->used++] = value;
  return;
}

And a primitive test harness, without full code coverage.

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

/* Crude testcase-checker.  Doesn’t even print the line number.
 */
bool test_int( const int got, const int expected )
{
  if (got == expected) {
    return true;
  } else {
    fflush(stdout);
    fprintf( stderr, "Case Failed: Expected %d, got %d.\n", expected, got );
    return false;
  }
}

int main(void)
{
  stack_t stack = STACK_INITIALIZER;
  bool passed_so_far = true;

  push( &stack, 1 );
  push( &stack, 2 );
  push( &stack, 3 );
  push( &stack, 4 );
  push( &stack, 5 );

  passed_so_far &= test_int( pop(&stack), 5 );
  passed_so_far &= test_int( pop(&stack), 4 );

  push( &stack, 6 );
  push( &stack, 7 );

  passed_so_far &= test_int( pop(&stack), 7 );
  passed_so_far &= test_int( pop(&stack), 6 );
  passed_so_far &= test_int( pop(&stack), 3 );
  passed_so_far &= test_int( pop(&stack), 2 );
  passed_so_far &= test_int( pop(&stack), 1 );

  // pop(&stack); // Causes an assertion to fail.

  if (passed_so_far) {
    printf("All test cases passed.\n");
    return EXIT_SUCCESS;
  }

  return EXIT_FAILURE;
}