[자료구조]큐(Queue) - 리스트

연결 리스트로 큐를 구현하면 동적 할당의 성질에 의해 메모리의 한계까지 큐의 크기를 늘릴 수도 있고, 또 큐가 아주 작을 때에도 메모리도 조금 밖에 차지하지 않는다. 단순 연결 리스트를 이용하여 큐를 구현하는 것은 약간의 무리가 있다. 

큐를 구현하려면 앞 노드의 위치와 뒷 노드의 위치를 모두 알고 있어야 하므로 할 수 없이 이중 경결 리스트를 사용하여야 한다. 

#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->next = tail;
    head->prev = head;
 
    tail->next = tail;
    tail->prev = head;
}
 
void clear_queue(void){
    dnode* temp_node;
    dnode* del_node;
    temp_node = head->next;
 
    while (temp_node != tail){
        del_node = temp_node;
        temp_node = temp_node->next;
        free(del_node);
    }
    head->next = tail;
    tail->prev = head;
}
 
 
int put(int value){
    dnode* temp;
    
    if ((temp = (dnode*)malloc(sizeof(dnode))) == NULL){
        printf("\n out of memory");
        return -1;
    }
 
    // 연결
    tail->prev->next = temp;
    temp->prev = tail->prev;
    temp->next = tail;
    tail->prev = temp;
 
    // 값 너어주기
    temp->key = value;
 
    return value;
}
 
int get(void){
    dnode* temp;
    int value;
    temp = head->next;
 
    if (temp == tail){
        printf("\n Queue underflow");
        return -1;
    }
 
    value = temp->key;
    head->next = temp->next;
    temp->next->prev = head;
    free(temp);
 
    return value;
}
 
void print_queue(void){
    dnode* temp;
    temp = head->next;
 
    printf("\n Queue contnes : Front  ---- >  Rear \n");
 
    while (temp != tail){
        printf("%-6d", temp->key);
        temp = temp->next;
    }
}
 
 
void main(void){
    init_queue();
 
    put(1);
    put(2);
    put(3);
    put(4);
    put(5);
    put(6);
 
    print_queue();
    get();
    print_queue();
    get();
    print_queue();
    get();
 
 
}