[자료구조] 큐

FIFO: First-In First-Out

왼쪽 끝에서 삭제 오른쪽 끝에서 삽입

 

front: 가장 최근에 삭제된 데이터의 index

rear: 가장 최근에 삽입된 데이터의 index

초기값은 둘 다 -1

 

모든 연산에 대한 시간 복잡도: O(1)

 

액션 전에 index를 바꾸고 액션

---

큐 ADT

create(max_size)	최대 크기 max_size인 공백큐 생성
init(q)	큐 초기화
enqueue(q, e)	q의 끝(rear)에 e를 추가
dequeue(q)	q의 맨 앞(front)에 있는 e를 제거하여 반환
peek(q)	q의 맨 앞(front)에 있는 e를 반환

---

선형큐

배열을 선형으로 사용

dequeue한 앞쪽 공간 재사용 불가

#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct{ //큐 선언
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
}QueueType;

void init_queue(QueueType* q){ //초기화 함수
    q->rear = -1;
    q->front = -1;
}

int is_full(QueueType* q){
    if(q->rear == MAX_QUEUE_SIZE - 1)
        return 1;
    else
        return 0;
}

int is_empty(QueueType* q){
    if(q->front == q->rear)
        return 1;
    else
        return 0;
}

void queue_print(QueueType* q){
    for(int i = 0; i < MAX_QUEUE_SIZE; i++){
        if(i <= q->front || i > q->rear)
            printf("	|");
        else // f<i<r일 때
            printf("%d	|", q->data[i]);
    }
    printf("\n");
}

void error(char* message){ //오류 함수
    printf("%s\n", message);
    exit(1);
}

void enqueue(QueueType* q, element item){
    if(is_full(q)){
        error("큐가 포화상태입니다");
        return;
    }
    q->data[++(q->rear)] = item;
}

element dequeue(QueueType* q){
    if(is_empty(q)){
        error("큐가 공백상태입니다");
        return -1;
    }
    int item = q->data[++(q->front)];
    return item;
}

---

원형큐

front: 첫번째 요소 하나 앞의 인덱스

rear: 마지막 요소의 인덱스

 

계산 후에 mod M 연산으로 인덱스를 정리해줘야함 

 

공백 상태: front == rear

포화 상태: front%M == (rear+1)%M

공백/포화 구분을 위해 하나의 공간은 항상 비워둔다 (front가 가리키고 있는 곳이 비어있음)

 

void init_queue(QueueType* q){ //초기화 함수
    q->rear = 0;
    q->front = 0;
}

int is_full(QueueType* q){
    return ((q->rear +1) % MAX_QUEUE_SIZE == q->front % MAX_QUEUE_SIZE);
}

int is_empty(QueueType* q){
    return (q->front == q->rear);
}

void queue_print(QueueType* q){
    printf("QUEUE(front = %d, rear = %d) = ", q->front, q-> rear);
    
    if(!is_empty(q)){ //비어있지 않을 때
        int i = q->front;
        do{ //i를 front로 설정했으니 do-while
            i = (i+1)%(MAX_QUEUE_SIZE);
            printf("%d |", q->data[i]);
            if(i == q->rear) break; //끝까지 가면 끝
        }while(i != q->front); //다시 front로 돌아오면 끝
    }
}

void enqueue(QueueType* q, element item){
    if(is_full(q)) error("큐가 포화상태입니다");
    
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

element dequeue(QueueType* q){
    if(is_empty(q)) error("큐가 공백상태입니다");
        
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

---

덱

double-ended queue

front/rear에서 모두 삽입/삭제가 가능한 큐

 

front: 현재 저장된 데이터들 중 가장 낮은 index - 1, data[front]는 항상 empty

rear: 현재 저장된 데이터들 중 가장 높은 index

 

void add_front(DequeYype* q, element item){
    if(is_full(q)) error("큐가 포화상태입니다");
    
    q->data[q->front] = item; //비어있던 front에 넣기 
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE //음수가 될 수 있기 때문에 M을 더해줌
}

 

element delete_rear(DequeType* q){
    int prev = q->rear;
    
    if(is_empty(q)) error("큐가 공백상태입니다");
    
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    
    return q->data[prev];
}