[C] Queue 리스트로 구현

[C] Queue 리스트로 구현

Queue를 리스트로 구현하게 되면, 동적으로 메모리를 할당할 수 있어 전체 메모리가 full 되지 않는한, overflow가 발생하지 않는다.

하지만 배열에 비해서 링크 처리를 해줘야 하며, 링크만큼의 크기를 차지한다.

큐는 처리에 지연이 발생할때, 입려된 명령이나 자료를 대기하기 위해 많이 사용한다.

특히 BIOS 키보드 버퍼나 마우스 이벤트를 큐에 저장하여 순서대로 처리하는데 사용한다.

#include <stdio.h> typedef struct _dnode{     int key;     struct _dnode *prev;     struct _dnode *next; }dnode; dnode *head, *tail; void init_queue(void){     head = (dnode*)malloc(sizeof(dnode));     tail = (dnode*)malloc(sizeof(dnode));     head->prev = head;     head->next = tail;     tail->prev = head;     tail->next = tail; } void clear_queue(void){     dnode *t;     dnode *s;     t = head->next;     while (t != tail){         s = t;         t = t->next;         free(s);     }     head->next = tail;     tail->prev = head; } int put(int k){     dnode *t;     if ((t = (dnode*)malloc(sizeof(dnode))) == NULL){         printf("\n  Out of memory.");         return -1;     }     t->key = k;     tail->prev->next = t;     t->prev = tail->prev;     tail->prev = t;     t->next = tail;     return k; } int get(void){     dnode *t;     int i;     t = head->next;     if (t == tail){         printf("\n  Queue underflow");         return -1;     }     i = t->key;     head->next = t->next;     t->next->prev = head;     free(t);     return i; } void print_queue(void){     dnode *t;     t = head->next;     printf("\n  Queue contents : Front -----------> Rear \n");     while (t != tail){         printf("%-6d", t->key);         t = t->next;     } } void main(void){     int i;     init_queue();     printf("\nPut 5, 4, 7, 8, 2, 1");     put(5);     put(4);     put(7);     put(8);     put(2);     put(1);     print_queue();     printf("\nGet");     i = get();     print_queue();     printf("\n   getting value is %d", i);     printf("\nPut  3, 2, 5, 7");     put(3);     put(2);     put(5);     put(7);     print_queue();     printf("\nPut 3");     put(3);     print_queue();     printf("\nInitialize queue");     clear_queue();     print_queue();     printf("\nNow queue is empty, get");     i = get();     print_queue();     printf("\n    getting value is %d", i);     return 0; }

출처: https://hyeonstorage.tistory.com/350?category=622873 [개발이 하고 싶어요]