자료구조 5(큐)

---

 

- 큐

스택과 달리 나중에 들어온 데이터가 나중에 나가는 선입선출(FIFO : First-in-first-out) 구조이며 은행의 업무를 보기 위해 줄을 서있는 사람들을 예시로 들 수 있다. 큐에서 삽입이 일어나는 곳을 후단(rear) 삭제가 일어나는 곳을 전단(front)이라고 한다.

---

- 큐의 추상자료형

create : 공백 큐를 생성

init : 큐를 초기화

is_empty : 큐가 공백상태인지 확인

is_full : 큐가 포화상태인지 확인

enqueue : 큐의 삽입 연산

dequeue : 큐의 삭제 연산

peek : 큐의 front의 값을 읽어서 반환

 

---

- 선형큐의 구현

#include <stdio.h>
#define MAX 10

typedef struct queue{
    int data[MAX];
    int front;
    int rear;
}Queue;

void init(Queue *q) {
    q->front = q->rear = 0;
}

void is_empty(Queue *q) {
    if(q->rear == q->front)
        printf("큐가 공백상태입니다. \n");
}

void is_full(Queue * q) {
    if(q->rear == MAX)
        printf("큐가 포화상태입니다. \n");
}

void enqueue(Queue *q, int data) {    //큐에 데이터추가
    q->data[q->rear++] = data;
}

int dequeue(Queue *q) {    //큐에 데이터삭제
    int remove;
    remove = q->data[q->front++];
    return remove;
}

int peek(Queue *q) {
    return q->data[q->front];
}

void print_queue(Queue *q) {    //큐에 있는 데이터출력
    int i;
    for(i = q->front; i < q->rear; i++)
        printf("[%d] ", q->data[i]);
    printf("\n");
}

int main(void){
    Queue q;
    
    init(&q);
    
    is_empty(&q);
    
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 4);
    enqueue(&q, 5);
    enqueue(&q, 6);
    enqueue(&q, 7);
    enqueue(&q, 8);
    enqueue(&q, 9);
    enqueue(&q, 10);
    print_queue(&q);
    is_full(&q);
    
    printf("dequeue(q) : [%d] \n", dequeue(&q));
    printf("dequeue(q) : [%d] \n", dequeue(&q));
    print_queue(&q);
    
    return 0;
}

실행화면

---

- 원형큐의 구현

#include <stdio.h>
#define MAX 10

typedef struct queue{
    int data[MAX];
    int front;
    int rear;
}Queue;

void init(Queue *q) {
    q->front = q->rear = 0;
}

void is_empty(Queue *q) {
    if(q->rear == q->front)
        printf("큐가 공백상태입니다. \n");
}

void is_full(Queue * q) {
    if((q->rear + 1) % MAX == q->front)
        printf("큐가 포화상태입니다. \n");
}

void enqueue(Queue *q, int data) {    //큐에 데이터추가
    q->rear = (q->rear + 1) % MAX;
    q->data[q->rear] = data;
}

int dequeue(Queue *q) {    //큐에 데이터삭제
    q->front = (q->front + 1) % MAX;
    return q->data[q->front];
}

int peek(Queue *q) {
    return q->data[q->front];
}

void print_queue(Queue *q) {    //큐에 있는 데이터출력
    int i;
    i = q->front;
    do{
        i = (i + 1) % MAX;
        printf("[%d] ", q->data[i]);
        if(i == q->rear)
            break;
    }while(i != q->front);
    printf("\n");
}

int main(void){
    Queue q;
    
    init(&q);
    
    is_empty(&q);
    
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 4);
    enqueue(&q, 5);
    enqueue(&q, 6);
    enqueue(&q, 7);
    enqueue(&q, 8);
    enqueue(&q, 9);
    enqueue(&q, 10);
    print_queue(&q);
    is_full(&q);
    
    printf("dequeue(q) : [%d] \n", dequeue(&q));
    printf("dequeue(q) : [%d] \n", dequeue(&q));
    print_queue(&q);
    
    return 0;
}

실행화면

---

- 덱

큐의 전단과 후단에서 모두 삽입, 삭제가 가능한 큐를 의미한다.(큐와 스택의 혼합)

---

- 덱의 추상자료형

create : 공백 덱을 생성

init : 덱을 초기화

is_empty : 덱이 공백상태인지 확인

is_full : 덱이 포화상태인지 확인

add_front : 덱의 전단 삽입 연산

add_rear : 덱의 후단 삽입 연산

del_front : 덱의 전단 삭제 연산

del_rear : 덱의 후단 삭제 연산

peek_front : 큐의 front의 값을 읽어서 반환

peek_rear : 큐의 rear의 값을 읽어서 반환

---