6 장. 스택 스택, 큐 리스트작업은시간과무관하게정의 스택과큐의작업은시간을기준으로정의 스택은가장나중삽입된데이터가먼저삭제되는특성의자료형을추상화 학습목표 추상자료형스택의개념을이해한다. 배열과연결리스트로구현할때의차이점을이해한다. 추상자료형리스트로구현하는방법을명확히이해한다. 스택의응용예, 특히깊이우선탐색방법을이해한다. 스택과재귀호출의연관성을이해한다. 1
스택 스택 들어온시간순으로데이터를쌓아갈때가장위에즉, 가장최근에삽입된위치에있는데이터를삭제하거나아니면거기에이어서새로운데이터를삽입할수있도록하는추상자료형 후입선출 ( 後入先出 ) LIFO(Last-In, First-Out: 라이포또는리포 ) LCFS(Last-Come, First-Served) cf. 큐 : 선입선출 ( 先入先出 ), FIFO(First-In, First-Out: 파이포또는피포 ) 2
스택 스택개념 3
스택 스택탑만접근가능 4
한쪽끝에서삽입, 삭제 스택탑, 푸쉬, 팝 삽입삭제위치를스택탑부근으로제한함 구현자료구조에서탑이아닌다른곳을접근할수있어도지않기로약속 하 5
주요작업 추상자료형스택 Create: 새로운스택을만들기 Destroy: 사용되던스택을파기하기 Push: 스택탑바로위에새로운데이터를삽입하기 Pop: 스택탑데이터를삭제하기 GetTop: 스택탑데이터를검색하기 IsEmpty: 현재스택이비어있는지를확인하기 IsFull: 현재스택이꽉차있는지를확인하기 GetSize: 현재스택에들어가있는데이터의개수를알려주기 6
추상자료형스택 액시엄 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
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
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
C 배열에의한스택 두가지탑인덱스 초기화방법이다름 푸쉬, 팝인덱스계산이달라짐 10
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
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
void Push(Nptr Top, int Item) C 연결리스트에의한스택 스택의삽입함수 { Nptr Temp = (Nptr)malloc(sizeof(node)); 새로운노드공간을확보하고 Temp->Item = Item; 넘어온데이터복사 Temp->Next = Top; 리키게 Top = Temp; 새노드가현재상태의첫노드를가 탑이새로운노드를가리키게 삽입, 삭제 반드시첫노드 이유는무엇인가. 13
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; 이전탑데이터리턴 14
void FreeList(Nptr Top ) { Nptr Temp = Top; while (Temp!= NULL) C 연결리스트에의한스택 연결리스트공간반납함수 리스트가완전히빌때까지 { Top = Top->Next; 탑포인터전진 free Temp; Temp = Top; 탑포인터백업 이전탑노드공간반납 15
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); Item 값을스택에삽입 int Pop( ); 스택탑의데이터값을리턴함 boolean IsEmpty( ); 비어있는지확인 boolean IsFull( ); 꽉차있는지확인 private: int Top; 스택탑의인덱스를추적 int Stack[MAX]; 정수형스택데이터최대 100개 16
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
C ++ 연결리스트에의한스택 코드 6-7: StackP.h (C++ Interface by Linked List) typedef struct { 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
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
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
추상자료형리스트에의한스택구현 코드 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
추상자료형리스트에의한스택구현 코드 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
추상자료형리스트에의한스택구현 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
스택응용예 백스페이스키 KY<bs>OTW<bs><bs>REA 순으로입력 최종결과는? 백스페이스는어느위치에작용하는가 24
스택응용예 연산자표현 중위표현 ( 中位, In-Fix Expression): 5 + 7 연산자 (Operator) 가피연산자 (Operand) 의가운데있는표현 후위표현 ( 後位, Post-Fix Expression) : 5 7 + 연산자가피연산자맨뒤로가는표현. RPN(Reverse Polish Notation) 2 5 + 3 * 1 - 의연산 25
코드 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
스택응용예 진법의변환 ( 예 : 10 진수에서 2 진수로 ) 27
스택응용예 스택과재귀호출비교 ( 문자열뒤집기 ) 주어진문자열을들어오는대로스택에푸쉬하였다고가정프로그래머가만든스택 : 사용자스택재귀호출에의한스택 : 시스템스택사용자스택이일반적으로더욱유리 스택 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]); 28
코드 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
스택응용예 노드 A 에서출발해서노드 F 로가는경로가존재하는가? 용어정리 정점 ( 頂點, 꼭지점, 마디, Node, Vertex) 간선 ( 間線, 邊, Edge) 인접노드 ( 隣接, Adjacent Node) 30
스택응용예 해결방법 갈수있는길을모두가보기그래도가는길이없다면가는길없는것으로결론소모적탐색 ( 消耗, Exhaustive Search) 깊이우선탐색 (DFS: Depth First Search) 소모적탐색방법의하나문자그대로깊이를우선적으로추구갈수만있다면끝까지깊숙이가본다. 만약갈길이없다면이전으로되돌아온다. 31
깊이우선탐색 노드 A 에서출발해서노드 F 로가는경로가존재하는가 목적지까지제대로간다. A-B-E-F 어떤도시로갔는데거기서더나갈곳이없는막다른곳이된다. A-G-H 어떤길을따라서계속원을그리며돈다. A-B-C-D-B-C-D 32
깊이우선탐색 어떤도시로갔는데거기서더나갈곳이없는막다른곳이된다. 규칙 : 막힌도시라면다시바로그이전도시로되돌아온다. 되돌아오는행위를백트래킹 (Backtracking) 이라함 ( 한수물러주기 ) 되돌아간곳에서막힌도시아닌다른곳을시도 선택된도시를계속적으로스택에푸쉬하면 스택의내용은 A 로부터출발해서지금까지거쳐온일련의도시 백트래킹은스택의팝. 직전에거쳐온도시로되돌아가는행위 어떤길을따라서계속원을그리며돈다. 규칙 : 한번가본도시는다시안간다. ( 재방문회피 ) 33
깊이우선탐색 A-G-H 에서백트래킹 다시 B 를시도 34
재방문회피 I 깊이우선탐색 스택내용이 ABCDBE 일필요가없음중간의 BCD를생략하고 ABE로갈수있음 35
재방문회피 II 깊이우선탐색 현재상태에서이미가본 G를방문할필요가있는가. 없다. 만약 G에서 F까지가는길이있었다면이전에 G로갔을때가봤을것이다. 그러한길이없어서백트래킹한것이다. 36
깊이우선탐색순서 I 깊이우선탐색 37
깊이우선탐색순서 II 깊이우선탐색 38
깊이우선탐색 A 에서 K 로가는길이있는가? 최종적으로백트랙에의해스택이비어버림. 그런경로가없음을의미함. 39
깊이우선탐색 코드 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"; 현재의스택탑이목적지와일치하면 가는길있다고대답 40
재귀호출에의한깊이우선탐색 DepthFirstSearch(Origin, Destination) { if (Origin = = Destination) 출발지와목적지가같으면 return YES"; 가는경로가있다고대답 else for (Each Unvisited Cities C Adjacent to Origin) 안가본인접도시에대해 DepthFirstSearch(C, Destination); 거기서부터목적지까지재귀 유사성 출발지에서목적지까지갈수있느냐의문제는출발지에서한걸음나아간도시에서목적지까지갈수있느냐의문제와동일 새로운탐색을위해출발하려는도시가이미목적지와같다면목적지까지가는경로가이미존재 ( 베이스케이스 ) 루프가다돌아서더이상안가본도시가없으면이전의호출함수로리턴된다. 이리턴하는행위가바로스택을사용한탐색에서의백트래킹 41