3장 - 스택과 큐

목차

• 1. C++의 템플릿
• 2. 스택 추상 데이터 타입
• 3. 큐 추상 데이터 타입
• 4. C++의 서브타입과 상속
• 5. 미로 문제
• 6. 수식의 계산

 

1. C++의 템플릿

템플릿이란 클래스와 함수들의 재사용성을 증대시키기 위하여 C++에서 제공하는 기법으로

같은 알고리즘으로 문제를 해결할 수 있을 때, 인수(매개변수)의 타입만 교체하고 싶을 때 사용한다.

예를 들어보자.

template <class T>
void add (T& a, T& b){
	T sum = a + b;
}

위의 코드 add함수를 보면 원래대로라면 사용자가 int형으로 인수를 받을지, float형으로 받을지를 모르기 때문에 int형 인수를 갖는 add와 float형을 인수로 갖는 add를 두 번 정의해 줘야 한다. 하지만 template 클래스로 정의함으로써 굳이 두 번 정의하지 않고도 하나의 add함수가 int형과 float형 인수를 받아들일 수 있게 되었다. 

 

컨테이너 클래스 : 여러 개의 데이터 객체들을 저장  ex) 배열, bag, stack 등등

 

bag 클래스에 대해 간단히 살펴보면

push와 pop 등의 멤버 함수로 이루어져 있는데, 이때 알아둬야 할 건 push연산을 실행할 때 bag의 크기를 고려하여 크기가 부족하다면 ChangeSize 함수를 통해 공간을 늘려줘야 한다는 것이다.

이때 ChangeSize함수는 bag의 공간을 두배로 늘려주는데, 이렇게 필요할 때마다 늘려주면 메모리 공간의 낭비를 줄일 수 있다.

 

2. 스택 추상 데이터 타입

스택(Stack)은 프로그래밍에서 자주 사용되는 데이터 타입으로 STL에 이미 구현되어 있으며,

#include <stack> 코드를 통해 쉽게 사용할 수 있다.

하지만 지금은 STL을 사용하지 않고 직접 stack을 구현할 것이다.

 

먼저 스택에 대해 살펴보면 스택은 LIFO(Last In First Out), 후입 선출 구조로 먼저 들어간 데이터가 마지막에 나오는 구조이다. 쉽게 생각해 보면 책을 여러 권 쌓았을 때 맨 아래에 있는 책부터 빼는 게 아니고 맨 위에 책부터 차례로 빼는게 스택을 설명하는 예이다.

 

스택에서 사용되는 용어로는 아래와 같은 것들이 있다.

활성 레코드(activation record) - 이전 스택에 대한 포인터, 복귀 주소, 지역변수, 매개변수

스택 오버플로우(stack overflow) - 메모리 가용 범위를 초과했을 때 발생하는 에러

 

스택은 아래의 링크에 구현해 놓았다.

 

3. 큐 추상 데이터 타입

큐(queue) 역시 스택과 마찬가지로 자주 사용되는 데이터 타입으로 이미 STL에 구현되어 있으며,

#include <queue> 코드를 통해 쉽게 사용할 수 있다.

 

큐는 스택과 다르게 FIFO(First In First Out), 선입선출 구조로 먼저 들어간 데이터가 먼저 나오는 구조다. 

양 끝이 뚫려있는 상자를 생각하면 이해하기 쉽다. 먼저 데이터가 들어가면 그 데이터가 앞쪽에 차례차례 쌓이게 되고 추출하고 싶으면 앞에서부터 추출하면 된다.

 

큐의 문제점은 원소를 추출하고 연산하는 데에 시간이 오래 걸린다는 점이다. 스택 같은 경우 가장 위의 것, 즉 가장 나중에 들어간 데이터를 꺼내 쓰기 때문에 상관없지만 큐 같은 경우 맨 앞의 데이터를 꺼내 썼다면 모든 데이터들을 다시 맨 앞으로 당겨와야 되기 때문에 시간이 오래 걸린다. 

 

이 문제점을 해결하기 위해 원형 큐라는 알고리즘을 도입하면 된다.

 

원형 큐의 알고리즘은 다음과 같다.

배열을 원형이라 생각해 보면 모든 배열 위치는 직전 위치와 다음 위치를 가지고 있다. 즉 원래의 큐라면 front는 직전 위치를 가지고 있지 않지만, 원형 큐의 front는 capacity-1이라는 직전 위치를 가지고 있다.

rear이 마지막 원소가 있는 위치를 가리키고 있다고 한다면 원형 큐의 원소의 삽입은 real을 시계방향으로, 원소의 삭제는 front를 시계방향으로 한 칸씩 이동한다고 생각하면 된다. 

따라서 front==rear이 될 때가 공백이 되게 되고 queue의 IsEmpty()의 True 반환 조건이 됨을 알 수 있다.

원형 큐는 이 front와 rear, capacity, 이 세 개의 변수만 가지고 멤버 함수들을 구현할 수 있다.

 

원형 큐의 구현은 아래의 링크에 구현해 놓았다.

 

4. C++의 서브타입과 상속

상속(Inheritance)은, ADT(추상 데이터 타입) 간의 상속 관계를 표현하는 데 사용된다. (계승이라고도 함)

IS-A(~의 하나이다) 관계라고도 한다.

예를 들어보면 (Galaxy Note 10+) IS-A (핸드폰) , stack(스택) IS-A bag(백) 등이 있다.

 

C++의 공용 상속은 : 로 나타내는데 이는 IS-A의 관계를 표현한 것이다.

예를 들어보면 class stack : public bag 이렇게 표현하고 stack은 파생 클래스, bag은 기본 클래스이다.

 

Virtual은 뒤에 4장에 가서 자세히 배우지만 지금 간단히 설명하자면

virtual -> 선언 : 기본 클래스, 구현 : 파생 클래스

즉 virtual을 멤버 함수의 선언 앞에 붙였을 경우 기본 클래스에서 멤버 함수를 정의하지 않고 파생 클래스에서 정의하는 데에 쓰일 수도 있고, 포인터 연산에 있어서도 사용되는데, 기본 클래스의 객체 타입의 포인터가 파생 클래스의 객체를 참조한다면 원래대로라면 기본 클래스의 멤버 함수를 사용하고 그 결과값을 반환한다. 이때 virtual을 사용하면 파생 클래스의 멤버함수를 사용할 수 있다. 나도 처음에는 이해가 안 됐지만 뒤의 4장에 가면 확실히 이해할 수 있다. 

 

상속의 의미:

• 파생 클리스(ex.stack)가 기본 클래스(ex.bag)의 모든 비전용(공용:public, 보호:protect) 멤버(데이터, 함수) 상속        -> 계승된 멤버들은 같은 접근 레벨을 가짐
• 계승받은 멤버 함수는 같은 프로토타입 유지-> 기본 클래스 인터페이스 재사용-> 구현은 다르게 할 수 있음 -> 생성자, 파괴자는 상속 불가!!

5. 미로 문제

미로 문제는 처음에 봤을 때는 반가웠다. 처음 봤을 때 당시 내가 bfs알고리즘 문제를 계속 풀고 있었는데 bfs알고리즘의 기초 문제가 바로 미로 문제이다. But 그러나 자료구조는 쉽자 않은 과목이었다. 자세히 공부하진 않았지만 이 책에서 나오는 대략적인 알고리즘을 살펴보면 아래와 같다.

1. 먼저 미로의 테두리를 둘러 모두 0으로 초기화시켜 미로의 바깥으로 나가는 경우를 없앤다.
2. 자신의 위치에서 8방위를 방문할 건데 이미 방문한 위치는 방문하지 않아야 한다.
3. 방문하는 곳의 데이터를 stack에 담아 놓고 계속해서 가능한 곳을 방문하다 막혔을 때 pop을 통해 돌아온다.
4. 스택에 담을 때 다음에 가야 할 위치를 담으면 스택에서 꺼내서 쓸 때 편리하다.

이렇게 해서 자료구조적으로 미로 문제를 해결할 수 있다. 따로 코드를 구현하진 않았다. 만약 시험에 나온다면 지금까지 공부했던 것으로 풀 수 있을 것 같다.

 

6. 수식의 계산

우리는 수식을 계산할 때, 연산자의 우선순위를 통해 계산을 한다. 그렇다면 컴파일러는 수식을 계산할 때 어떤 식으로 계산하는지에 의문을 가질 수 있다. (물론 나는 의문을 갖지 않았지만)

정답은 '후위 표기식으로 계산한다'이다. 수식을 표현하는 표기식에는 크게 전위, 중위, 후위 표기 식이 있다.

각각의 표기식은 서로 변환될 수 있으며(전위-> 후위, 후위-> 중위) 표기되는 방법은 다 다르다.

 

책에서는 후위 표기식으로 표현하는 방법이 설명되어있는데 먼저 수식을 후위 표기식으로 바꾸는 방법은 간단하다.

1. 수식을 연산자 우선순위에 맞게 괄호를 포함시키도록 작성한다. 
2. 모든 연산자를 해당하는 괄호 바깥쪽(오른쪽)으로 빼서 다시 작성한다.
3. 모든 괄호들을 제거하고 남는 수식이 후위 표기식으로 작성된 수식이 된다.

예를 들면 A/B-C+D*E-A*C라는 수식이 있다고 한다면

1. 괄호 작성 - (((A/B)-C)+(D*E))-(A*C)
2. 연산자 이동 - (((AB)/C)-(DE)*)+(AC)*-
3. 괄호 제거 - AB/C-DE*+AC*-

전위 표기식도 후위 표기식과 같은 과정으로 괄호 작성 후 연산자를 괄호 앞쪽으로 빼주면 만들 수 있다.

중위 표기식은 수식에서 변경할 과정이 따로 없기 때문에 작성하지 않았다.

 

이제 중위 표기식을 후위 표기식으로 변경하는 알고리즘을 살펴보자.

먼저 isp(in-stack priority)와 icp(in-coming priority)를 사용해야 하는데 이는 쉽게 말하면 연산자에 가중치를 주는 것이다. isp에서 주는 연산자의 가중치와 icp에서 주는 연산자의 가중치는 같은 연산자라 하더라도 분명 다를 수 있다.

이 알고리즘은 스택을 사용한다. 수식을 하나하나 token단위로 쪼개서 순서대로 스택에 넣는다.

이때 스택에 넣고 뺄 때 isp와 icp가 사용되는데 아래와 같다. 

 

'연산자는 자신의 isp가 새로운 연산자의 icp보다 산술적으로 작거나 같을 때 스택 밖으로 나온다.'

이 알고리즘에서는 '(' 연산자가 가장 중요한데 '('의 icp는 0이고 isp는 8이다. 나머지 연산자는 모두 icp, isp가 0보다 크고 8보다 작다.(스택의 empty를 알려주는, 즉 수식의 끝임을 알려주는 '#'연산자만 icp의 값이 8이다.)

이 뜻은  '(' 연산자에 따라 스택에서 나오고 들어가는 것이 결정된다는 것이다.

• 숫자가 들어오면 바로 출력
• ')' 연산자가 들어오면 '(' 연산자를 pop 할 때까지 모든 스택의 원소 pop(출력)
• 연산자가 들어오면 isp와 icp를 비교해 스택의 top에 있는 연산자의 isp가 들어오는 연산자의 icp보다 클 때까지 계속해서 pop(출력)

중위 표기식을 후위 표기식으로 바꾸는 알고리즘은 아래의 링크에 구현해 놓았다.

 

https://github.com/kimtaehyun98/- 

kimtaehyun98/-