큐(queue)와 덱(deque)

✔️ 큐(queue)

---

먼저 들어온 데이터가 먼저 나가는 자료구조

선입 후출 : FIFO First-In Frist-Out 

 

예시 : 식당에서 먼저 주문한 사람이 먼저 음식을 받는다.

큐 구조

쉽게 이해하기 위해 큐를 가로로

 

큐에는 선형 큐와 원형 큐가 있다. 

선형 큐는 배열처럼 일자 데이터 구조이고 원형 큐는 처음과 끝이 연결되어있는 데이터 구조이다.

 

 

❗ 선형 큐의 문제점

    dequeue()로 요소를 꺼내면 맨 앞자리가 비어있기 때문에 이를 채우기위해 뒤의 모든 요소들을 한 칸씩 앞으로 땡겨야

    하기에 효율적이지 않다. 

 

 

프로그램 상에서 어떻게 원형 큐를 구현할까?

우리는 아주 좋은 %(나머지 연산)을 알고 있다. 

(마지막인덱스 + 1) 자리로 인덱싱 접근이 오면 % (큐의 크기) 연산을 해주어서 다시 맨 앞자리에 접근하게 한다. 

이를 통해 원형처럼 만들 수 있다.

 

원형 큐

 

큐의 전단과 후단을 관리하기 위해 2개의 변수가 필요하다.

• front : 첫번째 요소 바로 앞의 인덱스
• rear : 마지막 요소 인덱스

❗ 주의!

큐의 처음 상태는 항상 front ==rear

 

큐 추상 데이터 타입

create(size) // 최대 크기가 size인 공백 큐를 생성

init(q) // 큐를 초기화

is_full(s) // if (front == (rear + 1) % 큐 크기) return TRUE; 아니라면 return False;

is_empty(s) // if(front == rear) return TRUE; 아니라면 return False;

enqueue(q, item) // 큐가 풀 상태이면 에러를 반환, 아니라면 큐 마지막 요소 뒤에 item 추가

dequeue(q) // 큐가 비어있다면 에러 반환, 아니라면 (front + 1) 요소를 꺼낸후(제거) 반환

peek(s) // 큐가 비어있다면 에러 반환, 아니라면 (front + 1) 요소를 반환(제거X)

 

공백과 포화상태 구별을 위해 하나의 공간은 항상 비워둔다. 

이유 : front와 rear은 처음에 0에서 시작한다. 그런데 rear이 마지막인덱스 +1을 하면 0으로 가기에 이러면 포화상태인지 공백상태인지 알 수 없기 때문이다. 

 

 

✔️ 동적할당 큐 구현

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int* data;
    int front;
    int rear;
    int capacity;
} Queue;

void init_Queue(Queue* q) {
    q->front = q->rear = 0;
    q->capacity = 5;
    q->data = (int*)malloc(q->capacity * sizeof(int)); // 동적 할당
}

void enqueue(Queue* q, int item) {
    // 가득차면 용량 늘리기
    if (is_full(q)) {
        q->capacity *= 2;
        q->data = (int*)realloc(q->data, q->capacity * sizeof(int));
    }
    // rear가 마지막 + 1 이 최대용량을 넘지 않게 처리
    q->rear = (q->rear + 1) % q->capacity;
    q->data[q->rear] = item;
}

int dequeue(Queue* q) {
    if (is_empty(q)) {
        fprintf(stderr, "Queue is empty\n");
        exit(1);
    }
    // front가 최대용량을 넘지 않게 처리 
    q->front = (q->front + 1) % q->capacity;
    return q->data[q->front];

}

int peek(Queue* q) {
    if (is_empty(q)) {
        fprintf(stderr, "Queue is empty\n");
        exit(1);
    }
    return q->data[q->front];
}

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

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

 

rear는 항상 +1 인 곳에 데이터를 넣으며 마지막 데이터를 가리킨다.

front는 처음 0에 있다가 +1인 곳의 데이터를 찾거나 반환한다. 

 

 

✔️ 덱(deque)

---

double-ended queue

전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

 

덱의 구조

 

기존 큐에서 front와 rear에 기능을 더 추가해주고 위치 감소에 대한 연산을 바꾸면된다.

 

front 추가사항 : enqueue() 기능 ,getFront() 기능

rear 추가사항 : dequeue() 기능, getRear() 기능

 

💠 위치 감소 연산

front = (front - 1 + capacity) % capacity;

rear = (front - 1 + capacity) % capacity;

 

capacity를 더하는 이유?
front가 0위치인 상태에서 앞으로 enqueue를 하는 경우
front는 0위치에 데이터를 넣고 -1 칸 뒤로 갈 것이다. 
하지만 -1 인덱스는 없다. 그렇기에 덱의 크기를 더하여 0 미만으로 떨어지는 것을 막는다.

 

✔️ 동적할당 덱 구현

typedef struct {
    int* data;
    int front;
    int rear;
    int capacity;
} Dedue;

// 초기화
void init_dueue(Dedue* d) {
    d->front = 0;
    d->rear = 0;
    d->capacity = 5;
    d->data = (int*)malloc(d->capacity * sizeof(int)); // 동적 할당
}

// rear 요소 추가
void add_rear(Dedue* d, int item) {
    // 가득차면 용량 늘리기
    if (is_full(d)) {
        d->capacity *= 2;
        d->data = (int*)realloc(d->data, d->capacity * sizeof(int));
    }
    d->rear = (d->rear + 1) % d->capacity;
    d->data[d->rear] = item;
}

// rear 요소 삭제
int delete_rear(Dedue* d) {
    if (is_empty(d)) {
        fprintf(stderr, "dueue is empty\n");
        exit(1);
    }

    int prev = d->rear;
    d->rear = (d->rear - 1 + d->capacity) % d->capacity;
    return d->data[prev];

}
// front 요소 추가
void add_front(Dedue* d, int item) {
    // 가득차면 용량 늘리기
    if (is_full(d)) {
        d->capacity *= 2;
        d->data = (int*)realloc(d->data, d->capacity * sizeof(int));
    }

    d->data[d->front] = item;
    d->front = (d->front - 1 + d->capacity) % d->capacity;
    
}
// front 요소 삭제
int delete_front(Dedue* d) {
    if (is_empty(d)) {
        fprintf(stderr, "dueue is empty\n");
        exit(1);
    }
    
    d->front = (d->front + 1) % d->capacity;
    return d->data[d->front];

}

// rear 요소 get
int get_rear(Dedue* d) {
    if (is_empty(d)) {
        fprintf(stderr, "dueue is empty\n");
        exit(1);
    }
    return d->data[d->rear];
}

// front 요소 get
int get_front(Dedue* d) {
    if (is_empty(d)) {
        fprintf(stderr, "dueue is empty\n");
        exit(1);
    }
    int index = (d->front + 1) % d->capacity;
    return d->data[index];
}

int is_full(Dedue* d) {
    return d->front == ((d->rear + 1) % d->capacity);
}

int is_empty(Dedue* d) {
    return d->front == d->rear;
}

 

 

 

 

🔖 참고자료

---

• C로 쉽게 풀어쓴 자료구조 - 생능출판사

 

• 본 그림들은 참고자료를 바탕으로 작성자가 직접 그린 그림입니다.