A very simple min-stack implementation using arrays to store signed integers. The stack is created with a user-specified size. Supports a pop, push, and current-minimum operation, all of which run in O(1) time. The tradeoff is that twice as much space is required as an equivalent implementation supporting a current-minimum operation running in O…

min_stack.c

// min_stack.c
// Austin Zheng

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

struct min_stack {
  int* v;          // This array represents the main stack, and contains actual values.
  int* m;          // This array represents the min stack, and contains an index into the v array.
  unsigned int v_ptr;    // This is a pointer to the next free main stack slot.
  unsigned int m_ptr;    // This is a pointer to the next free min stack slot.
  unsigned int size;    // How big the stack is.
};

struct min_stack* create_stack(unsigned int size) {
  // Create a new min stack. Returns a pointer to the newly allocated stack,
  //  or a null pointer (if malloc fails).
  struct min_stack* new_stack = malloc(sizeof(struct min_stack));
  if (!new_stack) return NULL;
  
  // Allocate the main array.
  int* v = malloc(size*sizeof(int));
  if (!v) {
    free(new_stack);
    return NULL;
  }
  
  // Allocate the min array.
  int* m = malloc(size*sizeof(int));
  if (!m) {
    free(v);
    free(new_stack);
    return NULL;
  }
  
  new_stack->v = v;
  new_stack->m = m;
  new_stack->v_ptr = 0;
  new_stack->m_ptr = 0;
  new_stack->size = size;
  
  return new_stack;
}

void destroy_stack(struct min_stack* s) {
  // Properly deallocate memory for the min stack s.
  free(s->v);
  free(s->m);
  free(s);
}

int push(struct min_stack* s, int val) {
  // Push the value val onto the min stack s. Returns 0 if successful, 1 
  //  otherwise.
  if (!s) return 1;
  if (s->v_ptr >= s->size) {
    printf("Error! Cannot push: stack is full.\n");
    return 1;
  }
  
  // Push the value onto the stack.
  s->v[s->v_ptr] = val;
  
  // Update the min stack, if necessary.
  // Update if this is the first item being pushed onto the stack, or the new
  //  value is smaller than the value at the top of the min stack.
  if (s->m_ptr == 0 || val < s->v[s->m[s->m_ptr-1]]) {
    s->m[s->m_ptr] = s->v_ptr;
    s->m_ptr++;
  }
  
  // Increment the main stack pointer.
  s->v_ptr++;
  return 0;
}

int pop(struct min_stack* s, int* status) {
  // Pop and return the value at the top of the min stack s. If successful, 
  //  status is 0.
  *status = 1;
  if (!s) return 0;
  if (s->v_ptr == 0) {
    printf("Error! Cannot pop: the stack is empty.\n");
    return 0;
  }
  
  // Pop the value off the stack.
  s->v_ptr--;
  int ret_val = s->v[s->v_ptr];
  
  // Update the min stack, if necessary.
  // If the currently popped value is at the top of the min stack, pop the 
  //  min stack as well.
  if (s->m[s->m_ptr-1] == s->v_ptr) {
    s->m_ptr--;
  }
  
  *status = 0;
  return ret_val;
}

int get_min(struct min_stack* s, int* status) {
  // Return the current minimum value in the min stack s. If successful, 
  //  status is 0.
  *status = 1;
  if (!s) return 0;
  if (s->m_ptr == 0) {
    return 0;
  }
  
  // Return the item in v pointed to by the top entry in m.
  *status = 0;
  return (s->v[s->m[s->m_ptr-1]]);
}

int main() {
#define NUM_ELEMENTS 50
  // Test framework.
  printf("Creating min stack with %d elements...\n\n", NUM_ELEMENTS);
  struct min_stack* s = create_stack(NUM_ELEMENTS);
  if (!s) {
    printf("Unable to create min stack! Aborting...\n");
    return 1;
  }
  
  // Push a few values.
  int status;
  printf("Pushing 10...\n");
  push(s, 10);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 7...\n");
  push(s, 7);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 3...\n");
  push(s, 3);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 12...\n");
  push(s, 12);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 14...\n");
  push(s, 14);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 1...\n");
  push(s, 1);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 8...\n");
  push(s, 8);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Pushing 2...\n");
  push(s, 2);
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  // Pop values a few times.
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Popped %d...\n", pop(s, &status));
  printf("Min value is %d.\n\n", get_min(s, &status));
  
  printf("Destroying stack...\n");
  destroy_stack(s);
  
  return 0;
}