제 3 장 스택과 큐

Transcription

1 제 3 장스택과큐 Copyright 2007 DBLAB, Seoul National University

2 템플릿함수 (1) 클래스와함수의재사용에기여 (1) 템플릿함수를사용하지않는경우 ( 예 ) 정수배열을위한선택정렬함수 SelectionSort( 프로그램 1.6) 부동소수점수의배열을정리하려면? 첫째행에서 int *a를 float *a로변경둘째행에서 정수 를 부동소수점수 로변경 11번째행에서 int를 float로변경 (2) 템플릿 / 인수화타입 (parameterized type) 을이용한해결 소프트웨어개발시간과저장공간을상당히절약 Copyright 2007 DBLAB, Seoul National University 2

3 템플릿함수 (2) 템플릿함수 SelectionSort 이용예 float farray[100]; int intarray[250];... // 이시점에서배열들이초기화된다고가정한다 SelectionSort(farray, 100); SelectionSort(intarray, 250); 템플릿인스턴스화를보여주는코드의일부 사용상의주의사항 <, = 및복사생성자 int 와 float 에대해서는자동적으로정의 사용자정의데이타타입에대해서는별도로정의하여야함 ( 예 ) SelectionSort 를이용해 Rectangle 배열을그넓이의비내림차순으로정렬 operator < 정의필요 지정연산자, 복사생성자는컴파일러의묵시적구현으로충분 Copyright 2007 DBLAB, Seoul National University 3

4 컨테이너클래스표현을위한템플릿이용 (1) 클래스의재사용에기여 (1) 컨테이너클래스 다수의데이타객체들을수용또는저장하는자료구조를표현하는클래스 ( 예 ) 배열, 백 (Bag) 객체들의삽입과삭제가가능 백 (Bag) 동일한원소가여러번나타남 원소위치, 삭제연산시어떤원소가제거되는지는문제안됨 삽입 : 해당원소를배열의첫번째가용위치에저장. 배열이만원인경우그크기를두배확장. 삭제 : 배열중앙위치원소삭제. 그오른쪽모든원소는한자리씩왼쪽으로이동. Pop: 삭제될원소를반환 Copyright 2007 DBLAB, Seoul National University 4

5 컨테이너클래스표현을위한템플릿이용 (2) (2) 템플릿클래스를이용한 Bag 의구현 어떠한데이타타입의객체들도저장가능 Bag 의클래스정의와클래스외부에있는모든자기멤버함수의정의앞에 template <class T> 의접두문을붙임 template <class T> class Bag { public: Bag (int bagcapacity = 10); ~Bag(); int Size() const; bool IsEmpty() const; T& Element() const; 템플릿클래스 Bag 을 int 와 Rectangle 로인스턴스화 Bag<int> a; Bag<Rectangle> r; void Push(const T&); void Pop(); private: T *array; int capacity; int top; } 템플릿클래스 Bag 의정의 Copyright 2007 DBLAB, Seoul National University 5

6 스택추상데이타타입 (1) 순서리스트의특별한경우 순서리스트 : A=a 0, a 1,, a n-1, n 0 스택 (stack) 톱 (top) 이라고하는한쪽끝에서모든삽입 (push) 과삭제 (pop) 가일어나는순서리스트 스택 S=(a 0,...,a n-1 ): a 0 는 bottom, a n-1 은 top 의원소 a i 는원소 a i-1 (0<i<n) 의위에있음 후입선출 (LIFO, Last-In-First-Out) 리스트 Copyright 2007 DBLAB, Seoul National University 6

7 스택추상데이타타입 (2) 원소 A,B,C,D,E 를삽입하고한원소를삭제하는예 Copyright 2007 DBLAB, Seoul National University 7

8 스택추상데이타타입 (3) 시스템스택 프로그램실행시함수호출을처리 함수호출시활성레코드 (activation record) 또는스택프레임 (stack frame) 구조생성하여시스템스택의톱에둔다. 이전의스택프레임에대한포인터 복귀주소 지역변수 매개변수 함수가자기자신을호출하는순환호출도마찬가지로처리 순환호출시마다새로운스택프레임생성 최악의경우가용메모리전부소모 Copyright 2007 DBLAB, Seoul National University 8

9 스택추상데이타타입 (4) 주함수가함수 a1 을호출하는예 함수호출뒤의시스템스택 Copyright 2007 DBLAB, Seoul National University 9

10 스택추상데이타타입 (5) 스택 ADT 구현 일차원배열 stack[] 사용 i번째원소는 stack[i-1] 에저장 변수 top은스택의최상위원소를가리킴 ( 초기 : top = -1, 공백스택을의미함 ) private: T *stack; int top; int capacity; // 스택원소를위한배열 // 톱원소의위치 // 스택배열의크기 template <class T> Stack<T>::Stack (int stackcapacity): capacity (stackcapacity) { if(capacity < 1) throw Stack capacity must be > 0 ; stack = new T[capacity]; top = -1; } Copyright 2007 DBLAB, Seoul National University 10

11 큐추상데이타타입 (1) 큐 (queue) 한쪽끝에서삽입이일어나고그반대쪽끝에서삭제가일어나는순서리스트 새로운원소가삽입되는끝 리어 (rear) 원소가삭제되는끝 프런트 (front) 선입선출 (FIFO, First-In-First-Out) 리스트 원소 A, B, C, D, E 를순서대로큐에삽입하고한원소를삭제하는예 Copyright 2007 DBLAB, Seoul National University 11

12 큐추상데이타타입 (2) 큐의구현 : 1 차원배열 queue[] 이용 (1) 큐의첫번째원소 (front) 원소를 queue[0] 로표현한큐 rear rear rear A B C B C B C D [0] [1] [2] [0] [1] [0] [1] [2] 원소를하나삭제한뒤의상태 원소를하나삽입한뒤의상태 - 삭제 (pop) : queue[0] 에있는앞원소를제거 삭제할때마다나머지원소들을왼쪽으로이동해야함 큐가 n개의원소를가질때, 삭제시 Θ(n) 시간이걸림 - 삽입 (push) : 배열크기조절시간을제외하면 Θ(1) 시간이걸림 Copyright 2007 DBLAB, Seoul National University 12

13 큐추상데이타타입 (3) 큐의구현 (2) 큐의첫번째원소를 queue[front] 로표현한큐 - 변수 front를사용하여큐의첫번째위치를항상유지 - 원소의삭제를 Θ(1) 시간에수행하기위한방법 - 큐의원소 : queue[front],, queue[rear] front rear rear rear front front A B C B C B C D 첫번째원소를삭제한뒤의상태 원소를하나삽입한뒤의상태 Copyright 2007 DBLAB, Seoul National University 13

14 큐추상데이타타입 (4) 큐의구현 (2) 큐의첫번째원소를 queue[front] 로표현한큐 ( 계속 ) - 배열 queue의크기가 capacity일경우, rear가 capacity-1과같고, front > 0 일때문제발생 - 배열의크기를확장하지않고어떻게원소를삽입할까? 큐의모든원소를왼쪽끝으로이동시켜오른쪽끝에공간을만드는방법 배열이동에많은시간소요 : 큐의원소수에비례 front rear front rear A B C D E A B C D E... (a) 이동전 원형큐를사용하는방법 (b) 이동후 큐가배열의끝에서되돌아오게하여최악의경우삽입, 삭제시간을 O(1) 으로한다. Copyright 2007 DBLAB, Seoul National University 14

15 큐추상데이타타입 (5) 원형큐 (Circular queue) 변수 front 는큐에서첫원소의위치보다시계방향으로하나앞위치를가리킴 변수 rear 는큐에서마지막원소의위치를가리킴 rear rear rear C C D C D B A B A B front front front (a) 초기 (b) 삽입 (c) 삭제 Copyright 2007 DBLAB, Seoul National University 15

16 큐추상데이타타입 (6) 원형큐 모든배열위치는직전위치와다음위치를가짐 capacity-1 의다음위치 = 0 0 의직전위치 = capacity-1 원형큐의동작을위해 front 와 rear 를시계방향으로이동시킴 if(rear == capacity-1) rear=0; else rear++; // (rear++ 은 rear = (rear+1)%capacity) 와동등 ) Private: T* queue; // 큐원소를위한배열 int front, // 첫번째원소로부터반시계방향으로한위치뒤 rear, // 마지막원소의위치 capacity; // 큐배열의크기 template <class T> Queue<T>::Queue (int queuecapacity): capacity (queuecapacity) { if(capacity < 1) throw Queue capacity must be > 0 ; queue = new T[capacity]; front = rear = 0; } ADT Queue를원형의배열로구현했을때의데이타멤버선언과생성자 Copyright 2007 DBLAB, Seoul National University 16

17 큐추상데이타타입 (7) 멤버함수 IsEmpty(), Front() 와 Rear() 구현 template <class T> inline bool Queue<T>::IsEmpty() { return front == rear; } Template <class T> Inline T& Queue<T>::Front() { if(isempty()) throw Queue is empty. No front element ; return queue[(front+1)%capacity]; } Template <class T> Inline T& Queue<T>::Rear() { if(isempty()) throw Queue is empty. No rear element ; return queue[rear]; } 큐의공백조건 : front == rear 큐의포화와공백을구분하기위해만원이되기전에큐의크기를증가시킨다. 즉, front == rear가공백인지포화인지구분하기위해최대원소수를 capacity가아니라 capacity-1로한다 Copyright 2007 DBLAB, Seoul National University 17

18 큐추상데이타타입 (8) Push 의구현 queue 의크기를두배로확장하는맞춤코드필요 queue [0] [1] [2] [3] [4] [5] [6] [7] C D C D E F G A B B E front = 5, rear = 4 (b) 만원이된원형큐를펼쳐놓은모양 A F G [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] front = 5 rear = 4 (a) 만원이된원형큐 C D E F G A B front = 5, rear = 4 (c) 배열을두배로확장한뒤의모양 (ChangeSize1D( 프로그램 3.3) 을이용하여확장 ) Copyright 2007 DBLAB, Seoul National University 18

19 큐추상데이타타입 (9) Push 의구현 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] C D E F G A B front = 13, rear = 4 (d) 세그먼트를오른쪽으로이동한뒤의모양 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] A B C D E F G front = 15, rear = 6 (e) 같은내용의다른모양 (1) 크기가두배되는새로운배열 newqueue를생성한다. (2) 두번째부분 ( 즉, queue[front+1] 과 queue[capacity-1] 사이에있는원소들 ) 을 newqueue의 0에서부터복사해넣는다. (3) 첫번째부분 ( 즉 queue[0] 와 queue[rear] 사이에있는원소들 ) 을 newqueue의 capacity-front-1에서부터복사해넣는다. Copyright 2007 DBLAB, Seoul National University 19

20 큐추상데이타타입 (10) Pop 의구현 연산시간 : O(1) lastop 변수사용 template <class T> void Queue<T>::Pop() {// 큐로부터원소를삭제한다. if(isempty()) throw Queue is empty. Cannot delete. ; front = (front+1)%capacity; queue[front].~t(); // T 를위한파괴자 } 배열 queue 의공간전부를사용할수있도록하는방법 큐에서수행된마지막연산을기록해둔다 삽입수행된뒤 : Push 로설정 삭제수행된뒤 : Pop 으로설정 큐에서의삭제 front == rear 일때 lastop 의값에따라큐가공백인지포화인지판단 ( Push 이면포화, Pop 이면공백 ) 큐의삽입, 삭제연산이느려짐 Copyright 2007 DBLAB, Seoul National University 20

21 C++ 의서브타입과상속 (1) 상속 (inheritance): 추상데이타타입간의서브타입 (subtype) 관계를표현 IS-A(~ 의하나이다 ) 관계 ex) 의자 : 가구의서브타입 (IS-A) 사자 : 포유류의서브타입 (IS-A) 직사각형 : 다각형의서브타입 (IS-A). Bag 과 Stack 간의관계 백 (bag): 단순히원소들이삽입과삭제가될수있는자료구조 스택 : 원소들이후입선출순서에따라삭제되는자료구조 ( 제한적 ) Stack은 Bag의하나 (IS-A) 즉 Stack은 Bag의서브타입 Copyright 2007 DBLAB, Seoul National University 21

22 C++ 의서브타입과상속 (2) C++ 의공용상속 (public inheritance) : IS-A 관계를표현 class Stack : public Bag { } 일반적인추상데이타타입을표현하는클래스 : 기본클래스 (base class) - Bag 추상데이타타입을표현하는클래스 : 파생클래스 (derived class) - Stack Virtual 멤버함수 선언 : 기본클래스 구현 : 파생클래스 Copyright 2007 DBLAB, Seoul National University 22

23 C++ 의서브타입과상속 (3) 상속의의미 파생클래스 (Stack) 가기본클래스 (Bag) 의모든멤버 ( 데이타와함수 ) 들을상속받음 그러나기본클래스의비전용 ( 공용, 보호 ) 멤버에만접근가능 상속된멤버들은기본클래스에서가졌던것과똑같은접근레벨을파생클래스에서도가짐 상속받은멤버함수는똑같은프로토타입 (prototype) 을유지함 기본클래스인터페이스 (interface) 재사용 파생클래스연산의구현이기본클래스의구현과달라야할경우에는기본클래스의구현을무시하고파생클래스에서재구현한다. Copyright 2007 DBLAB, Seoul National University 23

24 C++ 의서브타입과상속 (4) Queue ADT 도 Bag 의서브타입 선입선출순서로원소가삭제되어야하므로 Bag 보다더세분화된것 Queue 도 Bag 의한파생클래스로표현가능 Queue 와 Bag 의구현사이의유사성은 Bag 과 Stack 사이의유사성보다덜하여더많은연산이재정의되어야함 Copyright 2007 DBLAB, Seoul National University 24

25 미로문제 (1) 미로 (maze) 는 1 i m 이고 1 j p 인이차원배열 maze[m][p] 로표현 1 : 통로가막혀있음 0 : 통과할수있음 입구 maze[1][1] 출구 maze[m][p] 예제미로 ( 경로를찾을수있는가?) Copyright 2007 DBLAB, Seoul National University 25

26 미로문제 (2) 현재의위치 x : maze[i][j] NW N NE [i-1][j-1] [i-1][j] [i-1][j+1] W [i][j-1] X [i][j+1] E [i] [j] [i+1][j-1] [i+1][j] [i+1][j+1] SW S SE 가능한이동 i=1 이거나 m 또는 j=1 이거나 p 인경계선에있는경우가능한방향은 8 방향이아니라 3 방향만존재 경계조건을매번검사하는것을피하기위해미로의주위를 1 로둘러쌈 배열은 maza[m+2][p+2] 로선언되어야함 Copyright 2007 DBLAB, Seoul National University 26

27 미로문제 (3) 이동할수있는방향들을배열 move 에미리정의하는방법 struct offsets { int a, b; }; enum directions {N, NE, E, SE, S, SW, W, NW}; offsets move[8]; q move[q].a move[q].b N NE E SE S SW W NW 이동테이블 [I][j] 에서 SW, 즉 [g][h] 로이동 g = I + move[sw].a; h = j + move[sw].b; 미로이동시, 현재의위치와직전이동방향을저장한후한방향을선택한다. Copyright 2007 DBLAB, Seoul National University 27

28 미로문제 (4) 입구 출구 긴경로를가진미로 추가고려사항 : 세배열 maze, mark, move 를사용시 새로운 3 원소쌍 (i, j, dir) 의표현법만명기하면됨 가장최근에입력된 3 원소쌍 (i, j, dir) 을먼저제거하므로이리스트는스택이되어야함 path 에서배열 maze, mark, move 는전역적이라고가정 stack 은 items 의스택으로정의 struct Items { int x, y, dir; }; Copyright 2007 DBLAB, Seoul National University 28

29 미로문제 (5) Operator << Stack 과 Items 에대해다중화 friend 로선언되어 Stack 의전용데이타멤버접근가능 template <class T> ostream& operator<<(ostream& os, Stack<T>& s) { os << "top = " << s.top << endl; for (int i = 0; i <= s.top; i++) os << i << ":" << s.stack[i] << endl; return os; } ostream& operator<<(ostream& os, items& item) { return os << item.x << "," << item.y << "," << item.dir; } 연산자 << 의다중화 Copyright 2007 DBLAB, Seoul National University 29

30 수식의계산 (1) 수식 피연산자, 연산자, 분리자로구성 수식의의미를위해하기위해연산의수행순서를파악해야함 계산순서를고정하기위해각연산자에우선순위를지정해야함 우선순위연산자 1 마이너스부호,! 2 *, /, % 3 +, - 4 <, <=, >=, > 5 ==,!= 6 && 7 C++ 에서연산자의우선순위 예 ) X = A/B-C+D*E-A*C 의계산순서 X = (((A/B)-C)+(D*E))-(A*C) Copyright 2007 DBLAB, Seoul National University 30

31 수식의계산 (2) 식의표현 중위표기식 : A * B / C 후위표기식 : A B * C / 전위표기식 : / * A B C Copyright 2007 DBLAB, Seoul National University 31

32 후위표기식 후위표기식의장점 : 예 ) 괄호가불필요 연산자의우선순위가무의미 계산과정이간단 ( 왼편에서오른편으로스캔 ) 중위표기 : A/B-C+D*E-A*C 후위표기 : AB/C-DE*+AC*- 연산 T 1 = A / B T 2 = T 1 C T 3 = D * E T 4 = T 2 + T 3 T 5 = A * C T 6 = T 4 T 5 후위표기 T 1 C D E * + A C * - T 2 D E * + A C * - T 2 T 3 + A C * - T 4 A C * - T 4 T 5 T 6 그림 3.13 후위표기의계산과정 Copyright 2007 DBLAB, Seoul National University 32

33 중위표기에서후위표기로의변환 (1) 중위표기식을후위표기식으로변환하는알고리즘 (1) 식을전부괄호로묶는다. (2) 이항연산자들을모두자기오른쪽괄호로이동시킨다. (3) 괄호를전부삭제한다. 예 ) 수식 A/B-C+D*E-A*C. ((((A/B)-C)+(D*E))-(A*C)) AB/C-DE*+AC*- Note : 피연산자의순서는불변 Copyright 2007 DBLAB, Seoul National University 33

34 중위표기에서후위표기로의변환 (2) 예 ) A+B*C 로부터 ABC*+ 를생성 다음토큰 스택 출력 없음 A 공백공백 없음 A + + A B + AB * +* AB C +* ABC 완료공백 ABC*+ 예 ) A*(B+C)*D 로부터 ABC+*D* 를생성 다음토큰스택없음공백 A 공백 * * ( *( B *( + *(+ C *(+* ) * * * D * 완료공백 출력없음 A A A AB AB ABC ABC+ ABC+* ABC+*D ABC+*D* Copyright 2007 DBLAB, Seoul National University 34

35 중위표기에서후위표기로의변환 (3) 우선순위를기반으로스택킹 (stacking) 과언스택킹 (unstacking) 을수행 ( 괄호때문에복잡해짐 스택속에있을때는낮은우선순위의연산자처럼동작 그외의경우높은우선순위의연산자처럼동작 해결방법 : isp(in-stack precedence) 와 icp(incoming precedence) 사용 연산자는자신의 isp 가새로운연산자의 icp 보다산술적으로작거나같을때스택밖으로나온다. 연산자 ISP(In Stack Priority) ICP(In Coming Priority) ( 8 0 단항-,! 1 1 *, /, % ,,, 4 4 ==,!= 5 5 && #(eos) 8 Copyright 2007 DBLAB, Seoul National University 35