[책 정리] Chapter 06. 큐

yj 0·2022년 5월 19일
datastructure
0

자료구조

목록 보기
6/12

6.1 큐 추상 자료형

큐(queue): 먼저 들어온 데이터가 먼저 나가는 구조, 선입 선출(FIFO: First-In First-out) 특성을 지닌 자료구조

  • 스택: 삽입과 삭제가 같은 쪽에서 일어남
  • 큐: 삽입과 삭제가 다른 쪽에서 일어남, 삽입이 일어나는 곳 후단(rear), 삭제가 일어나는 곳 전단(front)

<ADT 6.1> 큐

객체: n개의 element 타입의 요소들의 순서 있는 모임
연산:
	create() ::= 큐 생성
    init(q) ::= 큐 초기화
    is_empty(q) ::= 큐가 비어 있는지 검사
    is_full(q) ::= 큐가 가득 찼는지 검사
    enqueue(q,e) ::= 큐의 뒤에 요소를 추가
    dequeue(q) ::= 큐의 앞에 있는 요소를 반환한 다음 삭제
    peek(q) ::= 큐에서 삭제하지 않고 앞에 있는 요소를 반환
Quiz
  1. 큐와 같은 입출력 형태를 선입선출(FIFO)라고 함
  2. enqueue(a), enqueue(b), enqueue(c) 연산 후에 dequeue() 연산을 하면 어떤 데이터가 삭제되는가? -> a가 삭제 됨

6.2 배열로 구현된 큐

선형 큐

선형 큐(linear queue): 1차원 배열을 이용해서 데이터를 삽입, 삭제하는 queue를 구현 하는 경우
1. front와 rear의 초기값은 -1
2. 데이터가 삽입되면 rear를 하나 증가, 그 위치에 데이터가 저장됨
3. 삭제할 때는 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터 삭제
단점: front와 rear의 값이 계속 증가만 하기 때문에 언젠가 배열의 끝에 도달하게 됨. 배열의 앞부분이 비어 있더라도 사용하지 못함. -> 따라서, 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 함

원형 큐

원형 큐: 선형 큐의 문제를 해결함, 배열의 처음과 끝이 연결되어 있다고 생각하는 큐
=> front, rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것
1. front와 rear의 초기값은 0, front는 항상 큐의 첫 번째 요소의 하나 앞, rear는 마지막 요소를 가리킴
2. 삽입 시에 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입 됨
3. 삭제 시에도front가 먼저 증가되고, 증단된 위치에서 데이터를 삭제 함
=> 원형 큐에서 하나의 자리는 항상 비워 둠 -> 포화 상태와 공백 상태를 구별하기 위해

  • front == rear이면 원형 큐가 공백인 상태가 되고, front가 rear보다 하나 앞에 있으면 포화 상태가 도미

원형 큐의 삽입과 삭제 알고리즘

  • front, rear를 원형으로 회전 시키야 함
    front <- (front + 1) mod MAX_QUEUE_SIZE;
    rear <- (rear + 1) mode MAX_QUEUE_SIZE;

<알고리즘 6.2.1> 원형 큐에서의 삽입 알고리즘

enqueue(Q,x)

rear <- (rear + 1) mod MAX_QUEUE_SIZE;
Q[rear] <- x;

<알고리즘 6.2.2> 원형 큐에서의 삭제 알고리즘

dequeue(Q)

front <- (front + 1) MAX_QUEUE_SIZE;
return Q[front];

원형 큐의 구현

<프로그램 6.2.1> 원형 큐 프로그램

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100
typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void error(const char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

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

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q){
    return (q->rear + 1 % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, element item){
    if(is_full(q)){
        error("overflow");
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q){
    if(is_empty(q)){
        error("underflow");
    }

    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

// 피크 함수
element peek(QueueType* q)
{
    if (is_empty(q)) {
        error("underflow");
    }

    return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}

int main(){
    QueueType q;
    init(&q);

    printf("front: %d, rear: %d\n", q.front, q.rear);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue(): %d\n", dequeue(&q));
    printf("dequeue(): %d\n", dequeue(&q));
    printf("dequeue(): %d\n", dequeue(&q));
    printf("front: %d, rear: %d\n", q.front, q.rear);
}

프로그램6.2.1결과

Quiz
  1. 선형 큐의 문제점? -> front와 rear의 값이 계속 증가만 하기 때문에 언젠가 배열의 끝에 도달하게 되고, 배열의 앞 부분이 비어 있어도 사용하지 못하는 문제가 있음
  2. 원형 큐에서 front와 rear가 가리키는 것? -> front: 첫 번째 요소로부터 시계방향으로 하나 앞, rear: 마지막 요소를 가리킴
  3. 크기가 10인 원형 큐에서 front와 rear가 모두 0으로 초기화되었다고 가정하고 다음과 같은 연산후에 front와 rear의 값을 말하라.
    enqueue(a), enqueue(b), enqueue(c), dequeue(), enqueue(d)
    -> front 1, rear 4

6.3 연결 리스트로 구현된 큐

연결된 큐(linked queue): 연결 리스트로 만들어진 큐
장점: 배열로 구현된 큐에 비해 크기가 제한되지 않음
단점: 코드가 더 복잡, 링크 필드 때문에 메모리 공간을 더 많이 사용

삽입 연산

  1. 동적 메모리 할당을 통해 새로운 노드를 생성
  2. 데이터를 저장하고 연결 리스트의 끝에 새로운 노드를 추가하면 됨
  • 큐가 공백 상태라면(front = rear = NULL) front, rear 모두 새로운 노드를 가리키도록 함
  • 큐가 공백이 아니고 기존 노드가 있는 경우라면 rear가 가리키고 있는 노드의 링크 필드가 새로운 노드를 가리키고, 다음에 rear가 이 새로운 노드를 가리키도록 변경하면 됨

<프로그램 6.3.1> 연결된 큐 삽입 연산

// 삽입 연산
void enqueue(QueueType *q, element item){
	QueueNode *tmp = (QueueNode*)malloc(sizeof(QueueNode));
    if(tmp == NULL){
    	error("memory allocate error");
    }else{
    	tmp->item = item; // 데이터 저장
        tmp->link = NULL; // 링크 필드를 NULL로 저장
        if(is_empty(q)){ // 큐가 공백이면
        	q->front = tmp;
            q->rear = tmp;
        }else{ // 큐가 공백이 아니면
        	q->rear->link = tmp; // 순서가 중요
        	q->rear = tmp;
    }
    
}

삭제 연산

삭제 연산: 연결 리스트의 처음에서 노드를 꺼내오면 됨

  • 큐가 공백이라면 오류
  • 큐가 공백이 아니라면 front가 가리니는 노드를 tmp가 가리키도록하고, front는 front의 링크 값으로 설정(front는 이전에 가리키는 노드의 다음 노드를 가리키게 됨)
  • tmp가 가리키는 노드로부터 데이터를 꺼내오고 동적 메모리 해제를 통해 노드를 삭제

<프로그램 6.3.2> 연결된 큐 삭제 연산

// 삭제 연산
element dequeue(QueueType *q){
	QueueNode *tmp = q->front;
    element item;
    if(is_empty(q)){ // 공백 상태
    	error("underflow");
    }else{
    	item = tmp->item; // 데이터를 꺼냄
        q->front = q->front->link; // front를 다음 노드를 가리키도로 함
        if(q->front == NULL){ // 공백 상태
        	q->rear = NULL;
        }
        free(tmp); // 노드 메모리 해제
        return item; // 데이터 반환
    }
}

연결된 큐 프로그램

<프로그램 6.3.3> 연결된 큐 프로그램

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100
typedef int element; // 요소의 타입
typedef struct QueueNode{ // 큐의 노드의 타입
    element item;
    struct QueueNode* link;
} QueueNode;
typedef struct { // 큐 ADT 구현
    QueueNode *front, *rear;
} QueueType;

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

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

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return (q->front == NULL);
}

// 삽입 함수
void enqueue(QueueType *q, element item){
    QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
    if(tmp == NULL){
        error("memory allocate error");
    }else{
        tmp->item = item;
        tmp->link = NULL;
        if (is_empty(q)) {
            q->front = q->rear = tmp;
        }else{
            q->rear->link = tmp;
            q->rear = tmp;
        }
    }
    
}

// 삭제 함수
element dequeue(QueueType *q){
    QueueNode* tmp = q->front;
    if(is_empty(q)){
        error("underflow");
    }else{
        element item = tmp->item;
        q->front = q->front->link;
        if(q->front == NULL){
            q->rear = NULL;
        }
        free(tmp);
        return item;
    }
}

// 피크 함수
element peek(QueueType* q)
{
    if (is_empty(q)) {
        error("underflow");
    }

    return q->front->item;
}

int main(){
    QueueType q;
    init(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue(): %d\n", dequeue(&q));
    printf("dequeue(): %d\n", dequeue(&q));
    printf("dequeue(): %d\n", dequeue(&q));
}

프로그램6.3.3결과

Quiz
  1. 연결된 큐에서 다음과 같은 연산 후의 상태를 그림으로 그려라.
    enqueue(a), enqueue(b), enqueue(c), dequeue(), enqueue(d)
  2. 연결된 큐가 공백 상태일 때 front와 rear의 값은? -> NULL이다.

6.4 덱

덱의 소개

덱(deque): double-ended queue의 줄임말, 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미
덱에서 가능한 연산: add_front(스택의 push), delete_front(스택의 pop, 큐의 dequeue), add_rear(큐의 enqueue), delete_rear, get_front, get_rear

덱의 추상 자료형

<ADT 6.4.1> 덱

객체: n개의 element형의 요소들의 순서 있는 모임
연산:
	create() ::= 덱을 생성
    init(dq) ::= 덱을 초기화
    is_empty(dq) ::= 덱이 공백 상태인지 검사
    is_full(dq) ::= 덱이 포화 상태인지 검사
    add_front(dq,e) ::= 덱의 앞에 요소를 추가
    add_rear(dq,e) ::= 덱의 뒤에 요소를 추가
    delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제
    delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제
    get_front(dq) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환
    get_rear(dq) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환

덱의 구현

  • 덱은 이중 연결 리스트로 구현됨
typedef int element; // 요소의 타입
typedef struct DlistNode{ // 노드의 타입
	element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
}DlistNode;

typedef struct DequeType{ // 덱의 타입
	DlistNode *head; // 첫 번째 노드를 가리키는 변수
    DlistNode *tail; // 마지막 노드를 가리키는 변수
}DequeType;

삽입 연산

<프로그램 6.4.1> 덱에서의 삽입 연산 add_rear

// 하나의 노도를 동적 메메로 할당에 의하여 생성하고 노드의 llink와 rlink 값을 함수의 매개변수 값으로 설정
DlistNode *create_node(DlistNode *llink, element item, DlistNode *rlink){
	DlinkNode *node =(DlistNode*)malloc(sizeof(DlistNode));
    if(node == NULL){
    	error("memory allocate error");
    }
    node->llink = llink;
    node->data = item;
    node->rlink = rlink;
    return node;
}

void add_rear(DequeType *dq, element item){
	DlistNode *new_node = create_node(dq->tail,item,NULL);
     if(is_empty(dq)){ // 덱이 공백이라면
    	dq->head = new_node; // head와 tail 모두 new_node가리킴
    }else{
		dq->tail->rlink = new_node; // tail 노드 다음 노도로 새로운 노드 추가
	}
    dq->tail = new_node; // tail 포인터 변경
}

<프로그램 6.4.2> 덱에서의 삽입 연산 add_front

void add_front(DequeType *dq, element item){
	DlistNode *new_node = create_node(NULL,item,dq->head);
    if(is_empty(dq)){ // 덱이 공백이라면
    	dq->tail = new_node; // head와 tail 모두 new_node가리킴
    }else{
    	dq->front->llink = new_node; // head 노드의 앞 노드로 새로운 노드 추가
    }
    dq->front = new_node; // head 포인터 변경
}

삭제 연산

  • delete_front 함수에서 첫 번째 노드를 삭제했을 경우, 덱이 공백이 아니라면 새로운 첫 번째 노드의 llink 필드를 NULL로 결정해야 함
  • 공백 상태가 되면 tail 포인터도 NULL로 만들어야 함

<프로그램 6.4.3> 덱에서의 삭제 연산 delete_front

element delete_front(DequeType *dq){
	element item;
    DlistNode *removed_node;
    if(is_empty(dq)) error("underflow");
    else{
    	removed_node = dq->head; // 삭제할 노드
        item = removed_node->data; // 데이터 추출
        dq->head = dq->head->rlink; // head 포인터 변경
        free(remove_node); // 메모리 공간 반납
        if(dq->head == NULL){ // 공백 상태라면
        	dq->tail = NULL;
        }else{ // 공백 상태가 아니라면
        	dq->head->llink = NULL; 
        }
    }
    return item;
}

<프로그램 6.4.4> 덱에서의 삭제 연산 delete_rear

element delete_rear(Dequeue *dq){
	element item;
    DlistNode * removed_node;
    if(is_empty(dq)) error("underflow");
    else{
    	removed_node = dq->tail; // 삭제할 노드
        item = removed_node->data; // 데이터 추출
        dq->tail = dq->tail->llink; // tail 포인터 변경
        free(removed_node); // 메모리 공간 반납
        if(dq->tail == NULL){ // 공백 상태라면
        	dq->head = NULL;
        }else{ // 공백 상태가 아니라면
        	dq->tail->rlink = NULL;
        }
    }
    return item;
}

덱 프로그램

<프로그램 6.4.5> 덱 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

void error(const char*message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init(DequeType *dq){
    dq->head = dq->tail = NULL;
}

int is_empty(DequeType *dq){
    return dq->head == NULL; // tail 포인터로 검사해도 상관 없음
}

void display(DequeType *dq){
    DlistNode* p;
    printf("(");
    for (p = dq->head; p != NULL;p = p->rlink){
        printf("%d ", p->data);
    }
    printf(")\n");
}

int main(){
    DequeType dq;

    init(&dq);
    add_front(&dq, 10); // 전단에 10 삽입
    add_front(&dq, 20); // 전단에 20 삽입
    add_rear(&dq, 30); // 후단에 30 삽입
    display(&dq); // 덱 내용 출력

    delete_front(&dq); // 전단에서 삭제
    delete_rear(&dq); // 후단에서 삭제
    display(&dq); // 덱 내용 출력
    
    return 0;
}

프로그램6.4.5결과

Quiz
  1. 덱을 큐처럼 사용하려면 어떤 연산들을 호출해야하는가? -> add_rear, delete->front
  2. 덱을 스택처럼 사용하려면 어떤 연산들을 호출해야하는가? -> add_front, delete-front

6.5 큐의 응용

버퍼

  • 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당함
  • 동일한 컴퓨터에서 생산자와 소비자 프로세스가 동시에 수행된다면 공유되는 큐를 동시에 접근할 수 있음
    -> 그런 경우 공유되는 큐를 사용하기 전에 큐를 사용한다고 먼저 락(lock)을 걸어야 함
    -> 내가 큐를 조작하고 있는 동안에 동시 수행되는 다른 프로세스가 큐를 건드리지 않도록하는 것임
QueueType buffer;

// 생산자 프로세스
producer(){
	while(1){
    	// 데이터 생산
        while(lock(buffer) != SUCCESS);
        if(!is_full(buffer)){
        	enqueue(buffer,데이터);
        }
        unlock(buffer);
    }
}

// 소비자 프로세스
consumer(){
	while(1){
    	while(lock(buffer) != SUCCESS);
        if(!is_empty(buffer)){
        	데이터 = dequeue(buffer);
            데이터 소비;
        }
        unlock(buffer);
    }
}

시뮬레이션

큐는 큐잉 이론에 따라 컴퓨터로 시스템의 특성을 시뮬레이션하여 분석하는데 이용
큐잉 모델: 고객에 대한 서비스를 수행하는 서비와 서비스를 받는 고객들로 이루어짐, 제한된 수의 서버로 인해 고객들은 서비스를 받기 위해 대기행렬에서 기다리게 됨
대기 행렬: 서비스를 받기 위해서 기다리는 것

ex)은행 서비스 시뮬레이션
1. 서비스 하는 행원은 한 사람으로 가정
2. 고객의 대기 행렬은 큐로 시뮬레이션 됨
3. 주어진 시간 동안 고객은 랜덤한 간격으로 큐에 들어옴
4. 고객들의 서비스 시간도 한계 값 안에서 랜덤하게 결정됨
5. 큐에 들어있는 고객들은 순서대로 서비스를 받기 시작함
5. 정해진 시간 동안 시뮬레이션이 끝나면 고객들의 평균 대기 시간을 계산하여 출력

<프로그램 6.5.1> 은행 서비스 시뮬레이션 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 100

typedef struct{
    int id;
    int arrival_time;
    int service_time;
} element;

typedef struct{
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

QueueType queue;

void error(const char*message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

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

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return q->front == q->rear;
}

// 포화 상태 검출 함수
int is_full(QueueType* q)
{
    return ((q->rear+1%MAX_QUEUE_SIZE) == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, element item){
    if(is_full(q)){
        error("overflow");
    }

    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;

}

// 삭제 함수
element dequeue(QueueType *q){
    if(is_empty(q)){
        error("underflow");
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

// 피크 함수
element peek(QueueType* q)
{
    if (is_empty(q)) {
        error("underflow");
    }
    return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}

// 0과 1 사이의 실수 난수를 생성하는 함수
double random(){
    return rand() / (double)RAND_MAX;
}

// 시뮬레이션에 필요한 여러 가지 상태 변수
int duration = 10; // 시뮬레이션 시간
double arrival_prob = 0.7; // 하나의 시간 단위에 도착하는 평균 고객의 수
int max_serv_time = 5; // 하나의 고객에 대한 최대 서비스 시간
int clock;

// 시뮬레이션 결과
int customers; // 전체 고객 수
int served_customers; // 서비스를 받은 고객의 수
int waited_time; // 고객이 기다린 시간

// 랜덤 숫자를 생성하여 고객이 도착했는지 도착하지 않았는지를 판단
int is_customer_arrived(){
    if(random() < arrival_prob){
        return true;
    }
    return false;
}

// 새로 도착한 고객을 큐에 삽입
void insert_customer(int arrival_time){
    element customer;
    customer.id = customers++;
    customer.arrival_time = arrival_time;
    customer.service_time = (int)(max_serv_time * random()) + 1;
    enqueue(&queue, customer);
    printf("Customer %d is come in at %d min Service time is %d min\n", customer.id, customer.arrival_time, customer.service_time);
}

// 큐에서 기다리는 고개을 꺼내어 고객의 서비스 시간을 반환
int remove_customer(){
    element customer;
    int service_time = 0;
    if(is_empty(&queue))
        return 0;
    customer = dequeue(&queue);
    service_time = customer.service_time - 1;
    served_customers++;
    waited_time += clock - customer.arrival_time;
    printf("Customer %d's service start at %d min Waited time is %d min\n", customer.id, clock,clock-customer.arrival_time);
    return service_time;
}

// 통계치를 출력
void print_stat(){
    printf("Service customer number = %d\n", served_customers);
    printf("Total waited time = %d\n", waited_time);
    printf("Waited time per one person = %f\n", (double)waited_time /served_customers);
    printf("Still waited customer number = %d\n", customers - served_customers);
}

// 시뮬레이션 프로그램
int main(){
    int service_time = 0;
    clock = 0;
    while(clock < duration){
        clock++;
        printf("Current time = %d\n", clock);
        if(is_customer_arrived()){
            insert_customer(clock);
        }

        if(service_time > 0){
            service_time--;
        }else{
            service_time = remove_customer();
        }
    }
    print_stat();
}

프로그램6.5.1결과

<참고자료>
천인국 · 공용해 · 하상호 지음,『C언어로 쉽게 풀어쓴 자료구조』, 생능출판(2016)

profile
yj 0
이전 포스트

[책 정리] Chapter 05. 스택

다음 포스트

[책 정리] Chapter 07. 트리

0개의 댓글