연결리스트로 구현된 스택

(1)

연결리스트로 구현된 스택

[제 12 주]

강 지 훈 jhkang@cnu.ac.kr 충남대학교 컴퓨터공학과

(2)

연결리스트로 구현된 스택

2

연결 리스트로

구현된 스택

(3)

연결리스트로 구현된 스택

3

사용자 관점에서의

스택의 공개함수

(4)

 Class STACK의 공개함수

 STACK 객체의 생성과 소멸

 STACK * STACK_new ()

 void STACK_free (STACK *s)

 STACK 객체의 점검

 boolean STACK_isEmpty (STACK * s)



스택이 empty 이면 TRUE를, 아니면, FALSE를 얻는다.

 boolean STACK_isFull (STACK * s)



스택이 full 이면 TRUE를, 아니면, FALSE를 얻는다.

 STACK 객체에게 행위를 지시

 void STACK_push (STACK * s, ELEMENT e)



스택에 e 를 삽입핚다.

 ELEMENT STACK_pop (STACK * s)



스택의 top에서 원소를 삭제하고 그 값을 얻는다.

연결리스트로 구현된 스택

4

(5)

연결리스트로 구현된 스택

5

스택의 구현

- 연결 리스트로 -

(6)

 Class STACK을 연결리스트로 구현

스택을 아래와 같은 형태로 만들려고 핚다.

연결리스트로 구현된 스택

6

a

0

top

a

₁

a

n-1

• length

(7)

 Class STACK의 속성들

typedef int ELEMENT ;

// ELEMENT 자료형은 응용에 따라 적절하게 정핚다.

typedef struct s_NODE NODE ; typedef struct s_NODE {

ELEMENT item ; NODE * next ; } NODE ;

typedef struct {

int length ; // 필요 없으면 삭제 가능 NODE * top ;

} STACK ;

연결리스트로 구현된 스택

7

(8)

 생성과 소멸

 STACK * STACK_new () { STACK * s ;

s = NewObject(STACK) ; s->top = NULL ;

return s ; }

 void STACK_free (STACK * s)

{ // There may be some elements in the stack.

FreeLinkedNodes(s->top) ; free(s) ;

}

연결리스트로 구현된 스택

8

(9)

 Push: Before & After

연결리스트로 구현된 스택

9

x

top y

s

length

e

x

top y

s

length

(10)

 Push: Step [0]

void STACK_push (STACK * s, ELEMENT e) {

① NODE * temp = NewObject(NODE) ; if ( STACK_IsFull(s) ) {

……

}

② temp->item = e ;

③ temp->next = s->top ;

④ s->top = temp ; }

연결리스트로 구현된 스택

10

x

top y

s

length

temp

(11)

 Push: Step [1]

void STACK_push (STACK * s, ELEMENT e) {

① NODE * temp = NewObject(NODE) ; if ( STACK_isFull(s) ) {

……

}

② temp->item = e ;

③ temp->next = s->top ;

④ s->top = temp ; }

연결리스트로 구현된 스택

11

x

top y

s

length

temp

①

(12)

 Push: Step [2]

void STACK_push (STACK * s, ELEMENT e) {

① NODE * temp = NewObject(NODE) ; if ( STACK_isFull(s) ) {

……

}

② temp->item = e ;

③ temp->next = s->top ;

④ s->top = temp ; }

연결리스트로 구현된 스택

12

x

top y

s

length

temp e

① ②

(13)

 Push: Step [3]

void STACK_push (STACK * s, ELEMENT e) {

① NODE * temp = NewObject(NODE) ; if ( STACK_isFull(s) ) {

……

}

② temp->item = e ;

③ temp->next = s->top ;

④ s->top = temp ; }

연결리스트로 구현된 스택

13

x

top y

s

length

temp e ③

① ②

(14)

 Push: Step [4]

void STACK_push (STACK * s, ELEMENT e) {

① NODE * temp = NewObject(NODE) ; if ( STACK_isFull(s) ) {

……

}

② temp->item = e ;

③ temp->next = s->top ;

④ s->top = temp ; }

연결리스트로 구현된 스택

14

x

top y

s

length

temp e ③

① ②

④

(15)

 Pop: Before & After

연결리스트로 구현된 스택

15

x top

m s

length u

x top

m s

length u

(16)

 Pop: Step [0]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ; return e ; }

연결리스트로 구현된 스택

16

x top

m s

length u

temp e

(17)

 Pop: Step [1]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ; return e ; }

연결리스트로 구현된 스택

17

x top

m s

length u

temp ① e

(18)

 Pop: Step [2]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ; return e ; }

연결리스트로 구현된 스택

18

x top

m s

length u

temp ① ^e x ②

(19)

 Pop: Step [3]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ; return e;

}

연결리스트로 구현된 스택

19

x top

m s

length u

temp ^e x ②

③

①

(20)

 Pop: Step [4]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ;

⑤ return e;

}

연결리스트로 구현된 스택

20

x top

m s

length u

temp ① ^e x ②

③

④

(21)

 Pop: Step [5]

ELEMENT STACK_pop (STACK * s) { ELEMENT e ;

① NODE * temp = s->top ; if ( STACK_IsEmpty(s) ) {

……

}

② e= temp->item ;

③ s->top = temp->next ;

④ free(temp) ;

⑤ return e;

}

연결리스트로 구현된 스택

21

x top

m s

length u

temp ① ^e x ②

③

④

⑤

(22)

 노드가 하나인 리스트에서의 삭제는?

앞서의 코드는 노드가 하나만 있는 경우에도 정상 적으로 작동하는가?

연결리스트로 구현된 스택

22

x top

s

length

(23)

연결리스트로 구현된 스택

23

요 약

(24)

 요약

연결 리스트

 사용권 (pointer, address, reference)

 삽입과 삭제

 배열과의 차이점, 장단점

연결리스트로 구현핚 스택

 공개함수는 변하지 않는다.

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

연결리스트로 구현된 스택

24

(25)

실 습

연결 리스트 (Linked List)

수식 계산

(26)

[실습] 수식 계산

26

문제 설명

(27)

 개요

문제 자체는 [제10주 실습] 프로그램과 동일

 사용자의 관점에서 완전 동일

 즉, 동일핚 목적을 달성해야 함



Postfix 수식을 입력 받아 계산 결과를 출력핚다.



[제10주 실습]에서와 동일하게 오류 처리를 핚다.

차이점은?

 스택의 구현만 다르다.

 스택의 구현을 제외핚 다른 모든 코드는 전혀 변경 없이 재활용핚다.

[실습] 수식 계산

27

(28)

 문제

입출력

 입력:



매번 postfix 수식의 문자열을 scanf()로 읽어 들인다.



문자열의 첫 문자가 „$‟이면 프로그램을 종료핚다.

 출력:



읽어 들인 postfix 수식을 계산하여 결과를 출력핚다.

[실습] 수식 계산

28

(29)

 입력되는 postfix 수식의 형식

토큰(token)의 표현

 문자 하나가 하나의 토큰



„0‟~ „9‟: 연산 값 (수식의 숫자는 1자리 정수만 허락하기로 함)



„+‟, „-‟, „*‟, „/‟, „%‟: 연산자 (C 언어와 동일핚 의미)



„\0‟: 문자열의 끝

수식의 표현

 토큰의 나열

예: 8 7 5 - / 9 4 - 1 2 + - *

[실습] 수식 계산

29

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

8 7 5 - / 9 4 - 1 2 + - * \0

(30)

 출력의 예

[실습] 수식 계산

30

> Postfix 수식을 입력하시오: 38- 3 : STACK <Bottom> 3 <Top>

8 : STACK <Bottom> 3 8 <Top>

- : STACK <Bottom> -5 <Top>

계산값 : -5

> Postfix 수식을 입력하시오: 57*8%

5 : STACK <Bottom> 5 <Top>

* : STACK <Bottom> 35 <Top>

% : STACK <Bottom> 3 <Top>

계산값 : 3

> Postfix 수식을 입력하시오: 875-/94-12+-*

5 : STACK <Bottom> 8 7 5 <Top>

- : STACK <Bottom> 8 2 <Top>

/ : STACK <Bottom> 4 <Top>

2 : STACK <Bottom> 4 5 1 2 <Top>

+ : STACK <Bottom> 4 5 3 <Top>

계산값 : 8

> Postfix 수식을 입력하시오: 82/3–42*+

/ : STACK <Bottom> 4 <Top>

– : STACK <Bottom> 1 <Top>

* : STACK <Bottom> 1 8 <Top>

+ : STACK <Bottom> 9 <Top>

계산값 : 9

> Postfix 수식을 입력하시오: 97%78*-253/+*

2 : STACK <Bottom> -54 2 <Top>

5 : STACK <Bottom> -54 6 5 <Top>

3 : STACK <Bottom> -54 6 5 3 <Top>

/ : STACK <Bottom> -54 6 1 <Top>

+ : STACK <Bottom> -54 7 <Top>

* : STACK <Bottom> -378 <Top>

계산값 : -378

> Postfix 수식을 입력하시오: $

<계산을 종료합니다>

(31)

 오류처리를 위한 보완

[제10주 실습]의 문제점을 파악하고 보완핚다.

 기본 내용은 동일

무엇이 문제인가?

 수식에 오류가 있다면?

 문자열의 길이가 스택의 용량을 넘으면?

[실습] 수식 계산

31

(32)

 오류를 포함한 출력의 예 (스택 크기 5)

[실습] 수식 계산

32

> Postfix 수식을 입력하시오: 38-- 3 : STACK <Bottom> 3 <Top>

-: STACK <Bottom> <Top>

[오류] 연산값에 비해 연산자의 수가 많습니다.

> Postfix 수식을 입력하시오: 57*8%9 5 : STACK <Bottom> 5 <Top>

[오류] 연산값에 비해 연산자의 수가 적습니다.

> Postfix 수식을 입력하시오: 123456+++++

4 : STACK <Bottom> 1 2 3 4 <Top>

5 : STACK <Bottom> 1 2 3 4 5 <Top>

6 : STACK <Bottom> 1 2 3 4 5 <Top>

[오류] 수식이 너무 길어 처리가 불가능합니다.

> Postfix 수식을 입력하시오: 82^

^ : STACK <Bottom> 8 2 <Top>

[오류] 수식에 알 수 없는 연산자가 있습니다.

> Postfix 수식을 입력하시오: 97%78*-253/+*

2 : STACK <Bottom> -54 2 <Top>

5 : STACK <Bottom> -54 6 5 <Top>

3 : STACK <Bottom> -54 6 5 3 <Top>

/ : STACK <Bottom> -54 6 1 <Top>

+ : STACK <Bottom> -54 7 <Top>

* : STACK <Bottom> -378 <Top>

계산값 : -378

> Postfix 수식을 입력하시오: $

<계산을 종료합니다>

(33)

[실습] 수식 계산

33

[실습 07-1]

main()의 구성

(34)

 Postfix 계산의 추상화

 main()의 관점에서는 postfix 계산에 대해서 자세히 알고 싶지 않다.

 단지 postfix 수식을 Postfix 객체에 넘겨주면, 그 Postfix 객체로부터 계 산 결과만 얻고 싶을 뿐이다.

 Postfix 계산을 Class로 !

[실습] 수식 계산

34

postfix

Postfix_setExpression() Postfix_eval ()

Postfix_computedValue() main()

inputPostfix()

“35+”

수식 전달

계산 지시

계산 값 얻어옴

(35)

 main()의 구성

#define MAXNUMEBROFTOKENS 200

#define MSG_StartingMessage “<Postfix 수식을 계산합니다>\n”

#define MSG_EndingMessage “\n<계산을 종료합니다>\n”

void main(void)

{ char expression[MAXNUMEBROFTOKENS] ; Postfix * postfix ;

boolean isInputEnded ; ; int returnCode ;

printMessage(MSG_StartingMessage) ; postfix = Postfix_new() ;

isInputEnded = inputPostfix(expression) ; while ( ! isInputEnded ) {

Postfix_setExpression(postfix, expression) ; returnCode = Postfix_eval(postfix) ;

if ( returnCode == ERROR_NONE ) {

printf(“계산값 : %d\n”, Postfix_computedValue(postfix)) ; } else {

outputErrorMessage(returnCode) ; } isInputEnded = inputPostfix(expression) ; } Postfix_free(postfix) ;

printMessage(MSG_EndingMessage) ; }

[실습] 수식 계산

35

(36)

[실습] 수식 계산

36

Class “Postfix” 의 공개함수

- [제10주 실습]의 것을 그대로 -

(37)

 Postfix의 공개함수

 Postfix * Postfix_new ()

 void Postfix_free (Postfix * postfix)

 void Postfix_setExpression (Postfix * postfix, char expression[])

 계산핛 수식 expression을 postfix 객체에 전달핚다.

 int Postfix_eval (Postfix * postfix)

 현재 객체가 가지고 있는 수식을 계산하도록 지시핚다.

 처리된 상태의 오류코드를 return 값으로 받는다.

 int Postfix_computedValue (Postfix * postfix)

 계산된 결과 값을 객체로부터 얻는다.

[실습] 수식 계산

37

(38)

[실습] 수식 계산

38

구현자적 관점에서의 Class “Postfix”의 구현

- [제10주 실습]의 것을 그대로 -

(39)

[실습] 수식 계산

39

Class “STACK” 의 공개함수

- 강의 자료를 볼 것 -

(40)

[실습] 수식 계산

40

구현자적 관점에서의 Class “STACK”의 구현

- Linked List로 -

- 강의 자료를 볼 것 -

(41)

[실습] 수식 계산

41

요 약

(42)

 생각해 볼 점

 스택의 구현이 바뀌었다!

 다른 프로그램 코드는 전혀 바뀌지 않고 완성되었는가?

 코드의 재활용과 공개함수의 관계는?

 공개함수는 구현을 감추고 있다고 생각되는가?

 라이브러리는 어떻게 여러 사람이 아무 문제 없이 잘 사용하고 있는가?

 요즈음의 소프트웨어는 매우 크다. 이미 개발되어 있는 라이브 러리를 많이 사용하고 있다.

 라이브러리의 구현자는 라이브러리의 내용을 아무 때나 마음대 로 바꿀 수 있는가?

 라이브러리 함수의 call 방법을 구현자가 마음대로 바꾸었다면 어떤 일이 벌어질까?

[실습] 수식 계산

42

(43)

[제 12 주] 끝

연결 리스트로 구현된 스택

(44)