연결리스트로 구현

큐 (Queue):

연결리스트로 구현

[제 13 주]

강 지 훈

주요 내용

 “큐 (Queue)” 란?

 연결리스트로 구현된 큐

“큐 (Queue)” 란?

 Queue

An ordered list in which all insertions take place at one end and all deletions take place at the opposite end.

Q = (a

, • • • , a

)

a_i+1 is behind a_i, 0 i  n-1.

FIFO ( First-In-First-Out ) list.

front

element rear element

 Example of a queue

“R” symbol points to the rear element in the queue.

“F” symbol points to the front element in the queue.

F R

E R E F R

C R D R D D E

B R B C R C C C D

A R A A B B B B C

F F F F F F F F addq(A) addq(B) addq(C) delq() addq(D) addq(E) addq(F) delq()

큐의 공개함수

 Class QUEUE의 공개함수

QUEUE 객체의 생성과 소멸

 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을 삽입핚다.

 ELEMENT QUEUE_delete (QUEUE *q)



큐의 front에서 ELEMENT를 삭제하고 그 값을 얻는다.

배열로 구현했을 때와

동일하다!!

큐의 구현

- 연결 리스트로 -

 연결 리스트를 사용한 큐

a₀ a₁ an-1

q front rear

 Class QUEUE의 속성

typedef struct s_NODE NODE ; typedef struct s_NODE {

ELEMENT e ; NODE * next ; } NODE ;

typedef struct {

NODE * front ; NODE * rear ;

int length ; // 필요핛 경우에만 } QUEUE ;

QUEUE * q ; // q 는 QUEUE 객체에 대핚 사용권을 갖게 된다.

a a a

q front rear

 생성과 소멸

 QUEUE * QUEUE_new() {

QUEUE * q ;

q = NewObject(QUEUE) ; q->front = NULL ;

q->rear = NULL ;

return q ; // At this point, q points an empty queue.

}

 void QUEUE_free (QUEUE * q) {

// There may be some elements in the queue.

freeLinkedNodes(q->front) ; free(q) ;

}

q front rear

 Rear에 삽입 [1]

q

a₀ a₁ an-1

front rear

q

a₀ a₁ an-1

front rear

e

 Rear에 삽입 [2]

q

a₀ a₁ an-1

front rear

e

temp ①

 Rear에 삽입 [3]

q

a₀ a₁ an-1

front rear

e

temp ①

②

 Rear에 삽입 [4]

void QUEUE_insert (QUEUE * q, ELEMENT e) {

……

}

q

a₀ a₁ an-1

front rear

e

temp ①

②

③

 삽입: 리스트가 비어 있다면 ?

비어 있지 않은 경우와 동일핚 코드로 가능핛까?

q

front rear

q front rear

e

 Front에서 삭제

a₀ a₁ an-1

q front rear

a₀ a₁ an-1

q front rear

 삭제: 리스트에 노드가 한 개만 있다면?

노드가 두 개 이상인 경우에 삭제하는 코드를 그대 로 사용핛 수 있을까?

q

a₀ front rear

q front rear

요 약

 요약

연결 리스트

사용권 (pointer, address, reference)

삽입과 삭제

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

연결리스트로 구현핚 큐

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

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

배열로 구현핚 큐

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

크기의 제핚을 받는다.

실 습

큐 (Queue)

연결 리스트로 구현된 큐

문제 설명

 문제

키보드에서 문자를 반복 입력 받는다.

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

입력의 종료 조건

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

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

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

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

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

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



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

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



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

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

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



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



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



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



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

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

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

숫자문자(„0‟ ~ „9‟): 해당 수 만큼 큐에서 삭제핚다.

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



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

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

„x‟ 라면)



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

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



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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

그 밖의 문자들: 다음과 같이 출력하고 무시핚다.

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

 출력의 예

<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()의 구성

 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”

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

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

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

필요핚 count들



입력된 문자의 수



무시된 문자의 수



삽입된 문자의 수



정상 처리된 문자의 수

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

count의 초기화

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

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

생성과 소멸

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)

void QAPP_esc (QAPP * app)

 필요한 공개(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”의 구현

 QAPP의 속성은?

typedef struct { QUEUE * q ;

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

 생성자와 소멸자의 구현

 QAPP * QAPP_new () {

QAPP * app ;

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

}

 void QAPP_free (QAPP * app) {

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

}

 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) ; }

 QAPP_Delete1(), QAPP_DeleteN()

 void QAPP_Delete1 (QAPP * 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 문자를 숫자로 ……

}

 QAPP_printAllFromFront()

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

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

 void QAPP_printAllFromBottom(QAPP * app) {

printf(“<Bottom> “) ;

QUEUE_printAllFromBottom(app->q) ; printf(“<Top>\n”) ;

}

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

 QAPP_Init(), QAPP_CountInput()

 void QAPP_initCharCounts (QAPP * app) {

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

 void QAPP_countInput (QAPP * app) {

app->inputChars++ ; }

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

 요약

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

응용에서 큐의 활용

어떻게 사용되는지

기본적인 공개함수

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

 응용에 따라...

큐의 구현

연결 리스트로 구현

포인터 다루기



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

[제 13 주] 끝

큐 (Queue)를 연결리스트로!!