C언어를 통한 자료구조(2)-queue

큐(queue)란 한쪽 끝에서만 push와 pop이 일어나는 스택과 달리 한쪽에서는 원소들의 push만 되고 반대쪽에서는 원소들의 pop만 이뤄지는 자료구조. 

한편, 이 자료구조는 가장 먼저 리스트에 삽입된 원소가 가장 먼저 삭제되므로 선입 선출(先入先出)인 FIFO(first in first out) 리스트라고도 부른다.

----Queue with linkedlist

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

typedef struct _node {
  int value;
  struct _node* next;
}node;

typedef node* nptr;

typedef struct _queue {
  int count;
  nptr top;
  nptr tail;
}queue;

void init(queue* qptr) {
  qptr->count = 0;
  qptr->top = NULL;
  qptr->tail = NULL;
}

void push(queue* qptr, int value) {
  nptr new_nptr = (nptr)malloc(sizeof(_node));
  new_nptr->value = value;
  new_nptr->next = NULL;
  if (qptr->top == NULL) {
    qptr->top = new_nptr;
  }
  else {
    qptr->tail->next = new_nptr;
  }
  qptr->tail = new_nptr;
  qptr->count++;
}

int pop(queue* qptr) {
  if (qptr->top != NULL) {
    nptr temp = qptr->top;
    qptr->top = temp->next;
    int pop_value = temp->value;
    free(temp);
    qptr->count--;
    return pop_value;
  }
  else {
    printf("No item is in this queue");
    return -1;
  }
}

int get_count(queue* qptr){
  return qptr->count;
}

void free_queue(queue* qptr) {
  while (qptr->top != NULL) {
    pop(qptr);
  }
  free(qptr);
}

int main() {
  queue* myqueue = (queue*)malloc(sizeof(queue));
  init(myqueue);

  push(myqueue, 1);
  push(myqueue, 2);
  push(myqueue, 3);
  push(myqueue, 4);
  push(myqueue, 5);
  push(myqueue, 6);

  printf("count: %d.\n", get_count(myqueue));

  printf("%d\n", pop(myqueue));
  printf("%d\n", pop(myqueue));
  printf("%d\n", pop(myqueue));
  printf("%d\n", pop(myqueue));
  printf("%d\n", pop(myqueue));

  free_queue(myqueue);
}