PowerPoint 프레젠테이션

Transcription

1 스택, 큐 6 장. 스택 리스트작업은시간과무관하게정의스택과큐의작업은시간을기준으로정의스택은가장나중삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형스택의개념을이해한다. 배열과연결리스트로구현할때의차이점을이해한다. 추상자료형리스트로구현하는방법을명확히이해한다. 스택의응용예, 특히깊이우선탐색방법을이해한다. 스택과재귀호출의연관성을이해한다. 1

2 Section 01 스택개념 - 스택 스택 들어온시간순으로데이터를쌓아갈때가장위에즉, 가장최근에삽입된위치에있는데이터를삭제하거나아니면거기에이어서새로운데이터를삽입할수있도록하는추상자료형후입선출 ( 後入先出 ) LIFO(Last-In, First-Out: 라이포또는리포 ) LCFS(Last-Come, First-Served) cf. 큐 : 선입선출 ( 先入先出 ), FIFO(First-In, First-Out: 파이포또는피포 ) 2

3 스택 스택개념 [ 그림 6-1] 식판스택 3

4 스택탑, 푸쉬, 팝스택탑만접근가능한쪽끝에서삽입, 삭제 삽입삭제위치를스택탑부근으로제한함구현자료구조에서탑이아닌다른곳을접근할수있어도하지않기로약속 [ 그림 6-2] 교과서스택 4

5 Section 02 추상자료형스택 - 추상자료형스택주요작업 Create: 새로운스택을만들기 Destroy: 사용되던스택을파기하기 Push: 스택탑바로위에새로운데이터를삽입하기 Pop: 스택탑데이터를삭제하기 GetTop: 스택탑데이터를검색하기 IsEmpty: 현재스택이비어있는지를확인하기 IsFull: 현재스택이꽉차있는지를확인하기 GetSize: 현재스택에들어가있는데이터의개수를알려주기 5

6 추상자료형스택 [ 그림 6-3] GetTop, Pop1( ), Pop2( ) 6

7 추상자료형스택액시엄 GetTop(Push(S, X)) = X Pop(Push(S, X)) = S IsEmpty(Create( )) = TRUE IsEmpty(Push(S, X)) = FALSE GetSize(Push(S, X)) = GetSize(S) + 1 7

8 Section 03 C에의한스택구현 - C 배열에의한스택코드 6-1: StackA.h (C Interface by Array) #define MAX 100 최대 100개데이터를저장 typedef struct { int Top; 스택탑의인덱스를추적 int Stack[MAX]; 스택데이터는정수형, 최대 100개 stacktype; 스택타입은구조체 void Push(stackType* Sptr, int Item); 스택데이터를정수로가정 int Pop(stackType* Sptr); 스택탑의데이터값을리턴함 void Init(stackType* Sptr); 스택초기화 bool IsEmpty(stackType* Sptr); 비어있는지확인 bool IsFull(stackType* Sptr); 꽉차있는지확인 8

9 C 배열에의한스택 코드 6-2: StackA.c (C Implementation by Array) #include <StackA.h> 헤더파일을포함 void Init(stackType* Sptr) 스택초기화함수 { Sptr->Top = 0; 탑인덱스 0으로빈스택을표시 boolean IsEmpty(stackType* Sptr) 비어있는지확인하는함수 { return (Sptr->Top = = 0); 탑인덱스 0이면 TRUE void Push(stackType* Sptr, int Item) 스택의삽입함수 { Sptr->Stack[Top++] = Item; 현재탑에삽입후탑인덱스를증가 IsFull 인지를미리확인해야함 int Pop(stackType* Sptr) 스택의삭제함수 { return Sptr->Stack[--Top]; 탑인덱스바로아래데이터를리턴 IsEmpty인지를미리확인해야함 9

10 C 배열에의한스택두가지탑인덱스 초기화방법이다름푸쉬, 팝인덱스계산이달라짐 [ 그림 6-4] 두가지탑인덱스 10

11 C 연결리스트에의한스택 코드 6-3: StackP.h (C Interface by Linked List) typedef struct { int Data; 스택데이터를정수형으로가정 node* Next; 다음노드를가리키는포인터변수 node; 노드는구조체타입 typedef node* Nptr; Nptr 타입이가리키는것은노드타입 void Push(Nptr Top, int Item); 스택데이터를정수로가정 int Pop(Nptr Top); 스택탑의데이터값을리턴함 void Init(Nptr Top); 스택초기화 bool IsEmpty(Nptr Top); 비어있는지확인 void FreeList(Nptr ); 연결리스트공간을반납 11

12 C 연결리스트에의한스택 코드 6-4: StackP.c (C Implementation by Linked List) #include <StackP.h> 헤더파일을포함 void Init(Nptr Top); 초기화함수 { Top = NULL; 탑포인터를널로 bool IsEmpty(Nptr Top); 빈스택인지확인하는함수 { return (Top = = NULL); 탑포인터가널이면 TRUE 12

13 C 연결리스트에의한스택 void Push(Nptr Top, int Item) 스택의삽입함수 { Nptr Temp = (Nptr)malloc(sizeof(node)); 새로운노드공간을확보하고 Temp->Item = Item; 넘어온데이터복사 Temp->Next = Top; 새노드가현재상태의첫노드를가리키게 Top = Temp; 탑이새로운노드를가리키게 삽입, 삭제 반드시첫노드이유는무엇인가 [ 그림 6-5] 스택푸시 13

14 C 연결리스트에의한스택 int Pop(Nptr Top) 스택의삭제함수 { if (Top = = NULL) 빈리스트이면 printf("empty Stack"); 오류처리 else { Nptr Temp = Top; 탑포인터를백업 int Item = Temp->Data; 이전탑데이터백업 Top = Top -> Next; 탑이다음노드를가리키게 free Temp; 이전탑노드공간반납 return Item; 이전탑데이터리턴 [ 그림 6-6] 스택팝 14

15 C 연결리스트에의한스택 void FreeList(Nptr Top ) 연결리스트공간반납함수 { Nptr Temp = Top; while (Temp!= NULL) 리스트가완전히빌때까지 { Top = Top->Next; 탑포인터전진 free Temp; 이전탑노드공간반납 Temp = Top; 탑포인터백업 15

16 Section 04 C++ 에의한스택구현 - C ++ 배열에의한스택 코드 6-5: StackA.h (C++ Interface by Array) const int MAX = 100; class stackclass { public: stackclass( ); stackclass(const stackclass& S); ~stackclass( ); void Push(int Item); int Pop( ); boolean IsEmpty( ); boolean IsFull( ); private: int Top; int Stack[MAX]; 생성자함수복사생성자함수소멸자함수 Item 값을스택에삽입스택탑의데이터값을리턴함비어있는지확인꽉차있는지확인스택탑의인덱스를추적정수형스택데이터최대 100개 16

17 C ++ 배열에의한스택 코드 6-6: StackA.cpp (C++ Implementation by Array) #include <StackA.h> stackclass::stackclass( ) 생성자함수 { Top = 0; 탑인덱스 0으로초기화 void stackclass::stackclass(const stackclass& S) 복사생성자 { Top = S.Top; 탑인덱스를복사 for (int Index = 0; Index <= S.Top; ++ Index) 인덱스 0부터 S.Top까지 Stack[Index] = S.Stack[Index]; 배열요소복사 stackclass::~stackclass( ) 소멸자함수 { 실행할일없음 boolean stackclass::isempty( ) 빈스택인지확인하는함수 { return boolean (Top = = 0); 탑인덱스 0 이면 TRUE 17

18 코드 6-7: StackP.h (C++ Interface by Linked List) typedef struct C ++ 연결리스트에의한스택 { int Data; 스택데이터를정수형으로가정 node* Next; 다음노드를가리키는포인터변수 node; 노드는구조체타입 typedef node* Nptr; Nptr 타입이가리키는것은노드타입 class stackclass { public: stackclass( ); stackclass(const stackclass& S); ~stackclass( ); void Push(int Item); int Pop( ); boolean IsEmpty( ); boolean IsFull( ); private: Nptr Top; 생성자함수복사생성자함수소멸자함수 Item 값을스택에삽입스택탑의데이터값을리턴함비어있는지확인꽉차있는지확인첫노드를가리키는포인터 18

19 C ++ 연결리스트에의한스택 코드 6-8: StackP.cpp (C++ Implementation by Linked List) #include <StackP.h> stackclass::stackclass( ) 생성자함수 { Top = NULL; 탑포인터값을널로세팅 stackclass::~stackclass( ) { int Temp; while (!IsEmpty( )) Temp = Pop( ); 소멸자함수 스택이완전히빌때까지 계속해서팝 boolean stackclass::isempty( ) 비어있는지확인하는함수 { return boolean(top = = NULL); 탑이널이면 TRUE 19

20 C ++ 연결리스트에의한스택 void stackclass::push(int Item) 스택의삽입함수 { Nptr NewTop = new Nptr; 새로운노드공간을확보하고 NewTop->Data = Item; 넘어온데이터복사 NewTop->Next = Top; 새노드가현재상태의첫노드를가리키게 Top = NewTop; 탑이새로운노드를가리키게 int stackclass::pop( ) 스택의삭제함수 { if (IsEmpty( )) 빈스택이라면오류처리 cout << "Deletion on Empty Stack"; else 빈스택이아니라면 { Nptr Temp = Top; 탑포인터를백업 int Item = Temp->Data; 탑노드의데이터를백업 Top = Top->Next; 탑이다음노드를가리키게 delete Temp; 이전탑노드공간반납 return Item; 이전탑데이터리턴 20

21 Section 05 리스트에의한스택구현 - 추상자료형리스트에의한스택구현 코드 6-9: StackL.h (C++ Interface by ADT LIST) #include <ListP.h> class stackclass { public: 코드 6-7( 또는코드 6-6) 과동일 private: listclass L; ; 리스트객체 스택클래스객체 S 는리스트클래스객체 L 을가짐 리스트클래스멤버함수사용을위해리스트클래스헤더파일 <ListP.h> 또는 <ListA.h> 를포함 21

22 추상자료형리스트에의한스택구현코드 6-10: StackL.cpp (C++ Implementation by ADT LIST) #include <StackL.h> stackclass::stackclass( ) 생성자함수 { stackclass::stackclass(const stackclass& S) 복사생성자함수 { L = S.L; 생성자함수 스택클래스객체 S 의 L 필드즉, S.L 필드는객체 S 가선언되는순간에생성 L 은리스트클래스객체이기때문에리스트클래스의생성자를통해초기화 복사생성자 stackclass A = B; 에의해스택클래스의복사생성자가불려옴 복사생성자내부에 A.L = B.L; 로선언되어있으므로결과적으로리스트클래스의복사생성자를부르게됨 22

23 추상자료형리스트에의한스택구현 boolean stackclass::isempty( ) { return boolean(l.isempty( )); void stackclass::push(int NewItem) { L.Insert(1, Item); void stackclass::pop( ) { L.Delete(1); void stackclass:gettop(int& Item) {L.Retrieve(1, Item); 빈스택인지확인하는함수푸쉬함수팝함수스택탑을읽는함수 추상자료형리스트위치기반리스트 리스트의처음위치를스택탑으로간주스택의푸쉬작업은리스트의처음위치에데이터를삽입하는것에해당스택의팝작업은리스트의첫데이터를삭제하는것에해당 23

24 Section 06 스택응용예 - 스택응용예백스페이스키 KY<bs>OTW<bs><bs>REA 순으로입력최종결과는? 백스페이스는어느위치에작용하는가 24

25 스택응용예연산자표현 중위표현 ( 中位, In-Fix Expression): 연산자 (Operator) 가피연산자 (Operand) 의가운데있는표현후위표현 ( 後位, Post-Fix Expression) : 연산자가피연산자맨뒤로가는표현. RPN(Reverse Polish Notation) * 1 - 의연산 [ 그림 6-7] * 1 - 의연산 25

26 스택응용예코드 6-11: 후위표현의연산 Read Symbol Ch 첫문자읽기 While Not End of Expression 수식의끝을만날때까지 { If Ch Is an Operand 읽은문자가피연산자이면 Push Ch 스택에푸쉬 Else 읽은문자가연산자이면 { Pop Operand2 두번째피연산자팝 Pop Operand1 첫번째피연산자팝 Result = Operand1 Ch Operand2 결과계산 Push Result 결과를스택에푸쉬 Read Symbol Ch 새로운문자읽기 Pop Stack and Print Result 결과를출력 26

27 스택응용예 진법의변환 ( 예 : 10 진수에서 2 진수로 ) [ 그림 6-8] 10 진수의 2 진변환 27

28 스택응용예스택과재귀호출비교 ( 문자열뒤집기 ) 주어진문자열을들어오는대로스택에푸쉬하였다고가정프로그래머가만든스택 : 사용자스택재귀호출에의한스택 : 시스템스택사용자스택이일반적으로더욱유리 스택 while (! StackIsEmpty) { NewCharacter = Pop( ) Print NewCharater 재귀호출 void Reverse(char S[ ], int First, int Last) { if (First > Last) return; else { Reverse(S, Fist+1, Last); printf("%c", S[First]); [ 표 6-1] 스택과재귀호출의비교 28

29 스택응용예 코드 6-12 괄호의매칭 InitializeStack( ); 스택초기화 Matched = TRUE; 매칭상태를표시하는변수초기화 while (Index < String.Length && Matched) 소스코드끝까지 { Character = String[Index++]; 새로운문자를읽어서 if (Character is '{') 여는중괄호이면 Push('{'); 스택에푸쉬 else if (Character is '') 닫는중괄호이면 { if (Not StackIsEmpty) 만약스택이비어있지않다면 Pop( ) 팝에의해여는괄호제거 else 스택이비어있다면 { Matched = FALSE; 매칭되는여는괄호가없었음 Break; 루프를빠져나감 여타문자는무시함 return Matched; 매칭결과를리턴 29

30 Section 07 깊이우선탐색 - 깊이우선탐색 노드 A 에서출발해서노드 F 로가는경로가존재하는가 목적지까지제대로간다. A-B-E-F 어떤도시로갔는데거기서더나갈곳이없는막다른곳이된다. A-G-H 어떤길을따라서계속원을그리며돈다. A-B-C-D-B-C-D [ 그림 6-9] 탐색을위한그래프 30

31 깊이우선탐색어떤도시로갔는데거기서더나갈곳이없는막다른곳이된다. 규칙 : 막힌도시라면다시바로그이전도시로되돌아온다. 되돌아오는행위를백트래킹 (Backtracking) 이라함 ( 한수물러주기 ) 되돌아간곳에서막힌도시아닌다른곳을시도선택된도시를계속적으로스택에푸쉬하면스택의내용은 A로부터출발해서지금까지거쳐온일련의도시백트래킹은스택의팝. 직전에거쳐온도시로되돌아가는행위 어떤길을따라서계속원을그리며돈다. 규칙 : 한번가본도시는다시안간다. ( 재방문회피 ) 31

32 깊이우선탐색 A-G-H 에서백트래킹 다시 B 를시도 [ 그림 6-10] 백트래킹 32

33 깊이우선탐색값재방문회피 I 스택내용이 ABCDBE 일필요가없음중간의 BCD를생략하고 ABE로갈수있음 [ 그림 6-11] 재방문회피 (1) 33

34 재방문회피 II 깊이우선탐색 현재상태에서이미가본 G 를방문할필요가있는가. 없다. 만약 G 에서 F 까지가는길이있었다면이전에 G 로갔을때가봤을것이다. 그러한길이없어서백트래킹한것이다. [ 그림 6-12] 재방문회피 (2) 34

35 깊이우선탐색 깊이우선탐색순서 I [ 그림 6-13] 깊이우선탐색순서 (1) 35

36 깊이우선탐색 깊이우선탐색순서 II [ 그림 6-14] 깊이우선탐색순서 (2) 36

37 깊이우선탐색 A에서 K로가는길이있는가? 최종적으로백트랙에의해스택이비어버림. 그런경로가없음을의미함. [ 그림 6-15] 깊이우선탐색순서 (3) 37

38 깊이우선탐색 코드 6-13: 깊이우선탐색 DepthFirstSearch(Origin, Destination) { S.Create( ); 새로운스택을만들기 Mark All Nodes as Unvisited; 일단모든도시를안가본도시로표시 S.Push(Origin); 출발지를푸쉬 Mark Origin as Visited; 푸쉬된도시는가본것으로표시 While (!S.IsEmpty( ) && Destination!= S.GetTop( )) { if (All Adjacent Cities Are Visited) 스택탑의인접도시가모두가본도시이면 S.Pop( ); 이전도시로되돌아감 else { Select a New City C; S.Push(C); 새로운도시를선택해서푸쉬 Mark C as Visited; 그도시를가본도시로표시 if (S.IsEmpty( )) return "No"; 스택이비어서빠져나오면 else 가는길없다고대답 return "YES"; 현재의스택탑이목적지와일치하면 가는길있다고대답 38

39 Section 08 스택과재귀호출 재귀호출에의한깊이우선탐색 DepthFirstSearch(Origin, Destination) { if (Origin = = Destination) 출발지와목적지가같으면 return YES"; 가는경로가있다고대답 else for (Each Unvisited Cities C Adjacent to Origin) 안가본인접도시에 DepthFirstSearch(C, Destination); 대해거기서부터목적지까지재귀 유사성 출발지에서목적지까지갈수있느냐의문제는출발지에서한걸음나아간도시에서목적지까지갈수있느냐의문제와동일 새로운탐색을위해출발하려는도시가이미목적지와같다면목적지까지가는경로가이미존재 ( 베이스케이스 ) 루프가다돌아서더이상안가본도시가없으면이전의호출함수로리턴된다. 이리턴하는행위가바로스택을사용한탐색에서의백트래킹 39

40 Thank you 40