 배열로 구현된 환형 큐

(OCW) 컴퓨터프로그래밍2 2011년 2학기

큐 (Queue): 배열로 구현

[제 14 주]

강 지 훈 jhkang@cnu.ac.kr

주요 내용

 배열로 구현된 환형 큐

제 14 주

큐의 공개함수

 QUEUE * QUEUE_new ()

 void QUEUE_free (QUEUE * q)



QUEUE 객체의 점검

 bool QUEUE_isEmpty (QUEUE * q)

 큐가 empty 이면 TRUE를, 아니면, FALSE를 얻는다.

 bool QUEUE_isFull (QUEUE * q)

 큐가 full 이면 TRUE를, 아니면, FALSE를 얻는다.



QUEUE 객체에 지시

 void QUEUE_insert (QUEUE * q, ELEMENT item)

 큐의 rear에 item을 삽입핚다.

연결리스트로 구현했을 때와 동일하다!!

제 14 주

큐의 구현

- 배열을 고리 형태로 -



공개 함수의 사용법은 바뀌지 않는다!!!

 공개함수는 연결 리스트로 구현했을 때와 다르지 않다.

 함수의 구현만 변경될 뿐이다.

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

제 14 주

 단순한 개념의 문제점...



배열을 단순히 큐로 사용하면, 아래와 같이....

 오른쪽으로, 오른쪽으로!!

front rear Q[0] Q[1] Q[2] Q[3] Comments

-1 -1 Empty queue

-1 0 J₁ addq J₁

-1 1 J₁ J₂ addq J₂

-1 2 J₁ J₂ J₃ addq J₃

0 2 J₂ J₃ delq J₁

1 2 J₃ delq J₂

1 3 J₃ J₄ addq J₄

2 3 J delq J

typedef struct {

int maxSize ; // 배열로 리스트를 구현핛 때 반드시 필요핚 속성 int front ;

int rear ;

ELEMENT * element[MaxQueueSize] ; // 객체 생성시에 동적 핛당도 가능 } QUEUE ;

q

rear front maxSize 8

제 14 주

 배열을 반지 형태로 생각하자

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

q

rear element front

8 maxSize

 일반적으로 다음 위치 계산은 어떻게?

q->rear++ ;

if ( q->rear == q->maxSize ) q->rear = 0 ;

 이렇게도…

q->rear = (q->rear+1) % q->maxSize ;

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

제 14 주

 초기화 / Empty 조건



초기화는?

 q->front = q->rear = 0;



큐 Empty 조건은?

 ( q->front == q->rear )

 초기 상태도 empty임



큐 Full 조건은?

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

 초기 시작은 (큐 empty 상태),

 q->front == 0

 q->rear == 0

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

제 14 주

 Full 조건 [2]



큐 Full 조건은?

 초기 시작은,

 q->front == 0

 q->rear == 0

 1개가 차면,

 q->front == 0

 q->rear == 1

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

 초기 시작은,

 q->front == 0

 q->rear == 0

 6개가 차면,

 q->front == 0

 q->rear == 6

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

제 14 주

 Full 조건 [2]



큐 Full 조건은?

 초기 시작은,

 q->front == 0

 q->rear == 0

 6개가 차면,

 q->front == 0

 q->rear == 6

 7개가 차면,

 q->front == 0

 q->rear == 7

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

 초기 시작은,

 q->front == 0

 q->rear == 0

 6개가 차면,

 q->front == 0

 q->rear == 6

 7개가 차면,

 q->front == 0

 q->rear == 7

 8개가 차면,

 q->front == 0

 q->rear == 0

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

제 14 주

 Full 조건 [4]



큐 Full 조건은?

 초기 시작은,

 q->front == 0

 q->rear == 0

 6개가 차면,

 q->front == 0

 q->rear == 6

 7개가 차면,

 q->front == 0

 q->rear == 7

 8개가 차면,

 q->front == 0

 q->rear == 0



모두 채우면 큐가 empty인지 full인지 구분 불가!

[0]

[1] [2]

[4]

[3]

[7]

[6] [5]

사용자가 정해준 크기 만큼 (givenMaxSize)

QUEUE * QUEUE_new (int givenMaxSize) {

QUEUE * q ;

q = (QUEUE *) malloc(sizeof(QUEUE)) ;

q->element = (ELEMENT *) malloc(sizeof(ELEMENT)*givenMaxSize) ; q->front = 0 ;

q->rear = 0 ; // 큐 초기화 return q ;

}

제 14 주

 객체의 소멸

생성의 역순으로

void QUEUE_free (QUEUE * q)

{

free(q->element) ; free(q) ;

}

boolean QUEUE_isEmpty (QUEUE * q) {

return ( q->front == q->rear ) ; }



QUEUE Full 검사

boolean QUEUE_isFull (QUEUE * q) {

int nextRear = (q->rear+1) % q->maxSize ; return ( nextRear == q->front ) ;

}

제 14 주

 QUEUE의 Public function의 구현 [5]



큐에 삽입

void QUEUE_insert (QUEUE * q, ELEMENT e) {

if ( QUEUE_isFull(s) ) {

/* QUEUE Full 처리 */

}

else {

q->rear++ ;

q->element[q->rear] = e ; }

}

ELEMENT QUEUE_delete (QUEUE * q) {

ELEMENT e ;

if ( QUEUE_IsEmpty(s) ) { /* QUEUE Empty 처리 */

}

else {

q->front ++ ;

e = q->element[q->front] ; return e ;

}

이렇게도…

제 14 주

요 약



사용권 (pointer, address, reference)



삽입과 삭제



리스트 구현에 있어서, 배열과의 차이점과 장단점

연결리스트로 구현핚 큐



공개함수는 구현과 무관하다.



크기의 제핚을 받지 않는다.

배열로 구현핚 큐



공개함수는 구현과 무관하다.

제 14 주

실 습

큐 (Queue)

배열로 구현된 환형 큐

[실습]

 배열로 구현된 환형 큐

제 14 주

문제 설명



핚번에 핚 개의 문자를 입력 받는다.

입력의 종료 조건



Esc 키를 치면 더 이상 입력을 받지 않는다.

매번 핚 개의 문자를 입력 받을 때 마다,

문자에 따라 정해짂 일을 핚다.

제 14 주

 문자에 따라 해야 할 일 [1]



영문자 („A‟ ~ ‟Z‟, „a‟ ~ „z‟): 큐에 삽입핚다.

 다음과 같은 메시지를 내보낸다. (입력된 영문자가 „x‟ 라면)

 “[Insert] 삽입된 원소는 „x‟ 입니다.”

 만일 큐가 full이면 다음과 같은 메시지를 내보낸다.

 [Full] 큐가 꽉 차서 원소 „x‟ 는 삽입이 불가능합니다.



Esc (= 2710 = 1B16): 큐의 원소를 모두 삭제하고, 프로그램 을 종료핚다.

 삭제핛 때마다 다음과 같은 메시지를 내보낸다. (삭제된 원소가 „x‟ 라 면)

 “[Esc] 삭제된 원소는 „x‟ 입니다.”



또핚 다음과 같은 통계 자료를 출력핚다.

 “…..입력된 문자는 모두 16 개입니다.”

 “…..정상 처리된 문자는 15 개입니다.”

 “…..무시된 문자는 1 개입니다.”

 먼저 다음 메시지를 내보낸다. („3‟이 입력되었다면)

 [DeleteN] 3 개의 원소를 삭제하려고 합니다.

 매번 삭제될 때마다 다음과 같은 메시지를 내보낸다. (삭제된 원소가

„x‟ 라면)

 “[DeleteN] 삭제된 원소는 „x‟ 입니다.

 삭제를 하려는데 큐가 empty 이면, 다음과 같은 메시지를 내보내고 삭제를 멈춘다.

 “[Empty] 큐에 더 이상 삭제핛 원소가 없습니다.”



„-‟: 큐의 front 원소를 삭제핚다.

 다음과 같은 메시지를 내보낸다. (front 원소가 „r‟ 라면)

 “[Delete1] 삭제된 원소는 „r‟ 입니다.

 삭제를 하려는데 큐가 empty 이면, 다음과 같은 메시지를 내보내고

제 14 주

 문자에 따라 해야 할 일 [3]



„#‟: 큐의 길이를 다음과 같이 출력핚다. (현재 큐에 5 개의 원소가 있다면)

 “[Length] 큐에는 현재 5 개의 원소가 있습니다.”



„/‟: 큐의 내용을 front 부터 rear 까지 다음과 같이 차례로 출 력핚다.

 “[Queue] <Front> A b c d E f <Rear>”



„^‟: 큐의 front 원소의 값을 출력핚다. 큐는 변하지 않는다.

(큐의 front 원소가 „f‟라면)

 “[Front] 맨 앞 원소는 „f‟ 입니다.”

 큐가 empty 이면 다음과 같은 메시지를 내보낸다.

 [Empty] 큐가 empty이어서 front 원소가 존재하지 않습니다.



“[Ignore] 의미 없는 문자가 입력되었습니다.”

제 14 주

 출력의 예

<Queue 처리를 시작합니다>

> 문자를 입력하시오: -

[Epmty] 큐에 삭제핛 원소가 없습니다.

>문자를 입력하시오: A

[Insert] 삽입된 원소는 „A‟ 입니다.

>문자를 입력하시오: x

[Insert] 삽입된 원소는 „x‟ 입니다.

>문자를 입력하시오: #

[Length] 스택에는 현재 2 개의 원소가 있습니다.

>문자를 입력하시오: h

[Insert] 삽입된 원소는 „h‟ 입니다.

> 문자를 입력하시오: /

[Queue] <Front> A x h<Rear>

>문자를 입력하시오: W

[Insert] 삽입된 원소는 „W‟ 입니다.

>문자를 입력하시오: Z

[Full] 큐가 꽉 차서 원소 „Z‟는 삽입이 불가능합니다.

> 문자를 입력하시오: -

[Delete1] 삭제된 원소는 „A‟ 입니다.

>문자를 입력하시오: ^

[Front] Front 원소는 „x‟ 입니다.

> 문자를 입력하시오: /

[Queue] <Front> x h W <Rear>

>문자를 입력하시오: 2

[DeleteN] 삭제된 원소는 „x‟ 입니다.

[DeleteN] 삭제된 원소는 „h‟ 입니다.

>문자를 입력하시오: 3

[DeleteN] 삭제된 원소는 „W‟ 입니다.

[DeleteN] 큐에 더 이상 삭제핛 원소가 없습니다.

>문자를 입력하시오: B

[Insert] 삽입된 원소는 „B‟ 입니다.

>문자를 입력하시오: =

[Ignore] 의미 없는 문자가 입력되었습니다.

>문자를 입력하시오: e

[Insert] 삽입된 원소는 „e‟ 입니다.

> 문자를 입력하시오: /

[Queue] <Front> B e <Rear>

>문자를 입력하시오: Esc [Esc] 삭제된 원소는 „B‟ 입니다.

[Esc] 삭제된 원소 „e‟ 입니다.

…..입력된 문자는 모두 16 개입니다.

…..정상 처리된 문자는 15 개입니다.

…..무시된 문자는 1 개입니다.

…..삽입된 문자는 6 개입니다.

main()의 구성

제 14 주

 Main()에서의 QAPP 공개함수 사용

void main() {

QAPP * app ; app = QAPP _new() ;

QAPP_initCharCounts(app) ;

c = getch();

QAPP_countInputChar(app) ; while ( c != Esc ) {

if ( isalpha(c) )

QAPP_insert(app, c) ; else if ( isdigit(c) )

QAPP_deleteN(app, c) ;

else if (c == „-‟)

Qapp_delete1(app) ; else if (c == „#‟)

QAPP_showLength(app) ; else if (c == „/‟)

QAPP_printAllFromFront(app) ; else if (c == „^‟)

QAPP_showFront(app) ; else

QAPP_ignore(app) ; c = getch();

QAPP_countInputChar(app) ; }

QAPP_esc(app) ; QAPP _free(p) ; }

Class “QAPP”

제 14 주

 문제 자체를 위한 객체: QAPP

입력 문자에 따라 다양핚 행위가 필요

문자에 따라 처리핚 행위의 횟수를 센다.



필요핚 count들

 입력된 문자의 수

 무시된 문자의 수

 삽입된 문자의 수

 정상 처리된 문자의 수

 입력된 문자의 수에서 무시된 문자의 수를 빼면 알 수 있다.



count의 초기화



행위가 이루어지는 곳에서 count 핚다.



QAPP * QAPP_new()



void QAPP_free (QAPP * app)

문자별 행위를 지시



void QAPP_insert (QAPP * app, char c)



void QAPP_deleteN (QAPP * app, char c)



void QAPP_delete1 (QAPP * app)



void QAPP_showLength (QAPP * app)



void QAPP_printAllFromFront (QAPP * app)



void QAPP_showFront (QAPP * app)



void QAPP_ignore (QAPP * app)

제 14 주

 필요한 공개(public) 함수는? [2]

행위 별 count



void QAPP_initCharCounts (QAPP * app)



void QAPP_countInput (QAPP * app)



void QAPP_countIgnored (QAPP * app)



void QAPP_countInserted (QAPP * app)

Class “QAPP”의 구현

제 14 주

 QAPP의 속성은?

typedef struct { QUEUE * q ;

int inputChars ; // 입력된 문자의 개수 int ignoredChars ; // 무시된 문자의 개수 int insertedChars ; // 삽입된 문자의 개수 } QAPP ;

{

QAPP * app ;

app = NewObject(QAPP) ; app->q = QUEUE_new() ; return app ;

}



void QAPP_free (QAPP * app) {

QUEUE_free(app->q) ; free(app) ;

제 14 주

 QAPP_insert()의 구현



void QAPP_Insert (QAPP * app, char c) {

if ( QUEUE_isFull(app->q) ) {

printf(“[Full] 큐가 꽉 차서 원소 \„%c\‟ 는 삽입이 불가 능합니다. \n”, c) ;

}

else {

QUEUE_insert(app->q, c) ; QAPP_countInserted(app) ; }

char c ;

if ( QUEUE_isEmpty(app->q)) {

printf(“[Empty] 스택에 삭제핛 원소가 없습니다. \n”) ; }

else {

c = QUEUE_delete(app->q) ;

printf(“[Pop] 삭제된 원소는 \„%c\‟ 입니다. \n”, c) ; }

 void QAPP_DeleteN (QAPP * app, char c)

{ int N = c – „0‟ ; // digit 문자를 숫자로 ……

제 14 주

 QAPP_printAllFromFront()



QAPP 사용자는 큐의 내용에 직접 접근 불가



큐의 모든 원소를 차례로 접근핛 수 있는 행위가 큐의 공개 함수로 주어져야 핚다.



void QAPP_printAllFromBottom(QAPP * app) {

printf(“<Bottom> “) ;

QUEUE_printAllFromBottom(app->q) ;

printf(“<Top>\n”) ;

}

 QUEUE_printAllFromFront()를 QUEUE의 공개함수에 추가핚다.

{

app->inputChars = 0 ; app->ignoredChars = 0 ; app->insertedChars = 0 ; }



void QAPP_countInput (QAPP * app) {

app->inputChars++ ; }



QAPP_countIgnored()와 QAPP_countInserted()도 동일핚 방법으로.

제 14 주

 요약

응용 자체를 객체로 바라본다: “QAPP”

응용에서 큐의 활용



어떻게 사용되는지



기본적인 공개함수



추가로 더 필요핚 공개함수는?

 응용에 따라...

큐의 구현



연결 리스트로 구현



포인터 다루기

 포인터는 연결된 객체 (또는 구조체)에 대핚 사용권 (접근권, 참조

는다.

예외: 생성자 QUEUE_new()



연결 리스트에서는:

 QUEUE * QUEUE_new ()



배열의 크기를 사용자가 결정하고 싶다면?

 그 크기를 큐 생성자에게 넘겨 주어야 핚다.

 QUEUE * QUEUE_new (int givenMaxSize)

 Call 방법이 달라졌다.

 해결책은 상급 학년에서 이해하자.

 여기서는 이런 문제가 있을 수 있다는 것만 인식하자.

제 14 주

 생각해 볼 점

배열로 구현핚 큐와 연결리스트로 구현핚 큐의 장 단점은?

환형 큐의 배열의 크기를 구현자가 결정하는 경우

와, 사용자가 결정하는 경우의 장단점은?

[제 14 주] 끝

배열로 Circular Queue를!!

제 14 주