[자료구조](6)[큐]

큐

큐: FIFO방식의 자료구조
먼저 들어온 것이 먼저 나간다

큐의 쓰임
작업 스케줄링
네트워킹

큐 ADT

• 데이터 <element, next_pointer>
  큐도 연결 리스트의 일종
• head: 큐의 맨 앞을 가리키는 포인터
• rear: 큐의 맨 뒤를 가리키는 포인터
• 연산
  endqueue(): 큐의 맨 뒤에 데이터 넣기
  dequeue(): 큐의 맨 앞에 있는 데이터 가져오고 삭제
  isFull(): 큐가 가득 찼는지 확인 <- 연결 리스트면 굳이?
  isEmpty(): 큐가 비었는지 확인 <- 연결 리스트면 굳이?

 

배열로 만든 큐

기본 골조는 다음과 같다.

const int MAX_SIZE = 5;
int queue[MAX_SIZE];
int head = -1, rear = -1; //큐가 비어있다는 뜻

isEmpty, isFull

bool isEmpty(int &head, int &rear){
    if (head == -1 && rear == -1) {return true;}
    else {return false;}
}

bool isFull(int &rear){
    if (rear == MAX_SIZE-1){return true;}
    else if (rear < head) {return true;}
    else {return false;}
}

enqueue

void enqueue(int value){
    if (isFull(head) == true)
        return;
    else{
        rear += 1;
        queue[rear] = value;
    }
}

dequeue

int dequeue(int &head){
    if (isEmpty(head, rear) == true)
        return 0;
    else{
        int value = queue[head];
        head -= 1;
        return value;
    }
}

-> 단순한 배열로 만든 큐는 공간 활용을 제대로 못한다!
    만약 크기가 3짜리 큐에서 enqueue x 3, dequeue x 3 을 한다면
    ■■■ (head = 0, rear = 2)
    □□□ (head = 3, rear = 2)
    이러면 지정된 공간에 데이터가 없어도 큐가 가득 차 못쓰게 된다.

    -> head, rear를 끝 지점에 도달하면 맨 앞으로 오게
    head%MAX_SIZE, rear%MAX_SIZE로 구현하면 효율적

 

연결 리스트로 만든 큐

스택과 마찬가지로 연결리스트에서 자료 삽입, 삭제에 제한, 특정 분야에서 더 효율적

이것 또한 연결 리스트로 구현해보겠다.

typedef struct node {
    int data; //int형 데이터 담음
    struct node* next; //node를 가리키는 포인터 선언
} Node;

Node* makeNode(int data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;  
    return newNode;
}

enqueue

Node* enqueue(int data, Node** rear){
    Node* newNode = makeNode(data);
    *rear->next = newNode;
    *rear = newNode;
}

dequeue

int dequeue(Node** top) {
    if (*head == NULL) {
        printf("queue is empty!\n");
        return -1;
    }
    int value = (*head)->data;
    Node* temp = *head;
    *head = temp->next; 
    free(temp); //할당한 다음 무조건 free!!
    return value;
}