min_queue.c

gistfile1.c

typedef struct node {
  int v;
  node *prev_min;
  node *next;
} node;

typedef struct {
  node *head;
  node *tail;
} min_queue;

int min_queue_append( min_queue *q, int v) {
  n = malloc(sizeof node);
  n->v = v;
  n->next = NULL;
  if (q->head == NULL) {
    q->head = n;
  }
  if (q->tail != NULL) {
    q->tail->next = n;
    n->prev_min = (q->tail->v < q->tail->prev_min->v) ? q->tail : q->tail->prev_min;
    q->tail = n;
  }
  else
  {
    q->tail = n;
    n->prev_min = NULL;
  }
}

int min_queue_pop( min_queue *q, int *v ) {

}

int min_queue_min( min_queue *q, int *min) {
  if (q->tail == NULL) { return -1; };
  if (q->tail->prev_min == NULL) { *min = q->tail->v; return 0};
  *min = (q->tail->v < q->tail->prev_min->v) ? q->tail->v : q->tail->prev_min->v;
  return 0;
}