414 - Fila do Recreio

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

typedef struct node Node;
struct node {
  int item;
  int priority;
  Node *next_node;
};

typedef struct pqueue PriorityQueue;
struct pqueue {
  Node *first;
};

PriorityQueue* create_priority_queue() {
  PriorityQueue *pqueue = (PriorityQueue*) malloc(sizeof(PriorityQueue));
  pqueue->first = NULL;

  return pqueue;
}

int is_empty(PriorityQueue *pqueue) {
  return (pqueue->first == NULL);
}

void free_list(Node *node) {
  if(node == NULL) return;

  free_list(node->next_node);

  free(node);
}

PriorityQueue* enqueue(PriorityQueue *pqueue, int item, int priority) {
  Node *new_node = (Node*) malloc(sizeof(Node));
  new_node->item = item;
  new_node->priority = priority;

  if (is_empty(pqueue) || (priority > pqueue->first->priority)) {
    new_node->next_node = pqueue->first;
    pqueue->first = new_node;
  } else {
    Node *current = pqueue->first;

    while ((current->next_node != NULL) && (current->next_node->priority > priority)) {
      current = current->next_node;
    }

    new_node->next_node = current->next_node;
    current->next_node = new_node;
  }

  return pqueue;
}

int dequeue(PriorityQueue *pqueue) {
  if (!is_empty(pqueue)) {
    Node *dequeued = pqueue->first;
    int item = dequeued->item;

    pqueue->first = dequeued->next_node;
    free(dequeued);

    return item;
  } else {
    return -1;
  }
}

int main() {
  PriorityQueue *lunch_queue;
  int n, m, i;

  scanf("%d", &n);

  for(n; n >= 1; --n) {
    lunch_queue = create_priority_queue();

    scanf("%d", &m);
    for(i = 1; i <= m; ++i) {
      int points;
      scanf("%d", &points);
      enqueue(lunch_queue, i, points);
    }

    int swaps = 0;
    for(i = 1; i <= m; ++i) {
      if(dequeue(lunch_queue) != i) ++swaps;
    }

    printf("%d\n", m - swaps);

    free_list(lunch_queue->first);
    free(lunch_queue);
  }

  return 0;
}