제 3 장 스택과 큐

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

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

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

컨테이너 클래스 표현을 위한 템플릿 이용(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; void Push(const T&); void Pop(); private: T *array; int capacity; int top; } 템플릿 클래스 Bag을 int와 Rectangle로 인스턴스화  Bag<int> a;  Bag<Rectangle> r; 템플릿 클래스 Bag의 정의

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

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

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

스택 추상 데이타 타입 (4) 주 함수가 함수 a1을 호출하는 예 함수 호출 뒤의 시스템 스택

스택 추상 데이타 타입 (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; }

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

큐 추상 데이타 타입 (2) 큐의 구현: 1차원 배열 queue[] 이용 큐의 첫번째 원소(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) 시간이 걸림

큐 추상 데이타 타입 (3) 큐의 구현 (2) 큐의 첫번째 원소를 queue[front]로 표현한 큐 - 원소의 삭제를 Θ(1) 시간에 수행하기 위한 방법 - 큐의 원소 : queue[front], …, queue[rear] rear rear rear front front front A B C … B C … B C D … 첫번째 원소를 삭제한 뒤의 상태 원소를 하나 삽입한 뒤의 상태

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

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

큐 추상 데이타 타입 (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를 원형의 배열로 구현했을 때의 데이타 멤버 선언과 생성자

큐 추상 데이타 타입 (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]; } Inline T& Queue<T>::Rear() if(IsEmpty()) throw “Queue is empty. No rear element”; return queue[rear]; 큐의 공백 조건 : front == rear 큐의 포화와 공백을 구분하기 위해 만원이 되기 전에 큐의 크기를 증가시킨다. 즉, front == rear가 공백인지 포화인지 구분하기 위해 최대 원소 수를 capacity가 아니라 capacity-1로 한다

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

큐 추상 데이타 타입 (9) Push의 구현 (1) 크기가 두배 되는 새로운 배열 newQueue를 생성한다. [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에서부터 복사해 넣는다.

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

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

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

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

C++의 서브타입과 상속(4) Queue ADT도 Bag의 서브 타입 Queue도 Bag의 한 파생 클래스로 표현 가능 Queue와 Bag의 구현 사이의 유사성은 Bag과 Stack 사이의 유사성보다 덜하여 더 많은 연산이 재정의 되어야 함

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

미로 문제(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]로 선언되어야 함

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

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

미로 문제(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; 연산자 <<의 다중화

수식의 계산(1) 수식 피연산자, 연산자, 분리자로 구성 수식의 의미를 위해하기 위해 연산의 수행 순서를 파악해야 함 계산 순서를 고정하기 위해 각 연산자에 우선순위를 지정해야 함 C++에서 연산자의 우선순위 예) X = A/B-C+D*E-A*C의 계산 순서 X = (((A/B)-C)+(D*E))-(A*C)

수식의 계산(2) 식의 표현 중위 표기식 : A * B / C 후위 표기식 : A B * C /

후위 표기식 후위 표기식의 장점: 예) 괄호가 불필요 연산자의 우선 순위가 무의미 계산 과정이 간단(왼편에서 오른편으로 스캔) 중위 표기: A/B-C+D*E-A*C 후위 표기: AB/C-DE*+AC*- 그림 3.13 후위 표기의 계산 과정

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

중위 표기에서 후위 표기로의 변환(2) 예) A+B*C로부터 ABC*+를 생성 예) A*(B+C)*D로부터 ABC+*D*를 생성

중위 표기에서 후위 표기로의 변환(3) 우선순위를 기반으로 스택킹(stacking)과 언스택킹(unstacking)을 수행 ‘(‘ 괄호 때문에 복잡해짐 스택 속에 있을 때는 낮은 우선순위의 연산자처럼 동작 그 외의 경우 높은 우선순위의 연산자처럼 동작 해결 방법 : isp(in-stack precedence)와 icp(incoming precedence) 사용 연산자는 자신의 isp가 새로운 연산자의 icp보다 산술적으로 작거나 같을 때 스택 밖으로 나온다.