2022. 4. 19. 22:11ㆍ강의 내용 정리/자료구조
Stack and queue
1. Stack이란?
1) Stack이란?
항목의 제거 및 추가가 Stack의 상단에서만 발생할 수 있는 정렬된 동족 항목의 그룹
- 같은 데이터 타입의 자료구조만 모아서 사용한다.
- Stack은 LIFO (Last In Fisrt Out) 구조이다.
cf) 메모리 상에서의 Stack: 지역변수를 저장하는 공간
cf) Call Stack: 함수를 호출할 때 추적하는 것을 의미하는데 함수가 호출될 때 스택 구조로 쌓이기 때문에 이를 Call Stack이라고 한다.
2) 멤버 함수 구현 시 주의 사항
- 요소를 pop할 때는 실질적으로 요소를 삭제할 필요가 없이 top의 위치만 조정하면 된다. 메모리 상에는 남아있지만 이를 사용할 수는 없다.
- pop 메소드는 마지막 데이터를 뽑아서 이를 반환한다.
- Robust한 프로그램을 만들기 위해 try throw를 통한 예외처리를 한다.
cf) PDF 파일을 보면 각 코드 줄마다 구현과정이 나옴
2. Class template
1) Class Template
- 형식 매개변수를 사용해 데이터 타입에 대한 여러 버전의 클래스를 생성할 수 있음
- 클래스 템플릿을 사용할 때는 어떤 타입에 대해 특정하게 처리하기 위해 사용하는 경우가 많음
- 컴파일 시 각 파일별로 코드를 생성하기에 클래스 템플릿을 분리하여 작성하면 링크 에러가 발생함
- 컴파일할 때 오브젝트 코드가 만들어지면서 symbol을 채워넣는데 클래스 템플릿을 사용하는 경우에는 데이터 타입을 알 수 없기에 에러가 발생한다.
- 컴파일 시간에 클래스를 만들기에 cpp 파일 내에 작성하거나 hpp 파일으로 작성함
cf) 클래스를 만들 때 cpp 파일과 h파일을 나눠서 만드는 이유는 cpp 파일에서 끌어와서 사용하면 다른 cpp 파일에서 함수 같은게 중복정의가 발생할 수 있기에 이를 방지하기 위해 헤더파일을 따로 만든다. 이때 클래스 템플릿의 경우 다른 파일에서 사용하기 위해선 hpp 파일을 끌고 와야하기에 위의 문제가 발생할 수 있다. 이에 따라 사용할 cpp 파일 위쪽에 해당 클래스를 선언하면 됨
2) Parameter
(1) 형식 파라미터
함수의 헤더에 적힌 파라미터
ex) void charStack.Push(ItemType newItem) 정의 시 newItem
- 함수를 정의할 때 사용하는 파라미터
- template<class ItemType>을 선언해 사용함
- 함수에 적힌 <ItemType> 또한 형식 파라미터에 해당
(2) 실제 파라미터
함수를 호출할 때 사용하는 파라미터
ex) charStack.Push(letter) 호출 시의 letter
(3) 클래스 템플릿을 아이템 타입으로 할 경우, 클래스를 아이템 타입으로 할 경우의 차이점
- 아이템타입을 클래스로 만들 경우에는 간단한 데이터 타입이더라도 객체로 만들어서 사용해야하기 때문에 그에 대한 연산 및 멤버 함수를 따로 만들어야함. 이에 따라 클래스 템플릿으로 사용하는게 좀 더 좋음
3. Array
1) Array란?
- 배열은 배열의 첫번째 메모리 주소를 가리키는 포인터 상수임
- char은 종료 시점에 널문자(\0)을 넣어 종료하는 구간을 알려줌
2) 변수의 세가지 정의
(1) 데이터 저장을 위한 공간
(2) 프로그램 내부에서 쓰일 식별자
(3) 메모리 주소
- 함수 또한 위와 같이 세가지 정의가 필요함
- 다른 언어와 연계하여 코드를 구현하는 경우가 있는데 이때 함수 이름이 mangling되어서 뭉개지면 이를 활용할 수 없음. 따라서 이러한 경우에 식별자가 중요해짐
3) Static/AUTOMATIC DATA/Dynamic
- 정적 데이터의 경우 프로그램이 끝날 때까지 데이터를 가지고 있다.
- AUTOMATIC DATA의 경우 일종의 지역변수처럼 동작한다.
- 동적 데이터의 경우 힙메모리에 저장이 되고 delete를 사용할 때 메모리를 할당 해제한다.
4) 동적 할당 시 주의 사항
- 동적 할당을 할 경우에는 할당 해제를 해야한다.
- 동적 배열로 정의했을 경우에는 배열 형태로 메모리 할당 해제를 진행해야한다.
ex) int *ptr = new char[5]; delete[] ptr; // delete ptr; (x)
- Dangling pointer문제가 발생하지 않게 주의해야한다.
cf) Dangling pointer: 두 개 이상의 포인터가 하나의 메모리 공간을 가리키고 있을 때 한 쪽에서만 데이터를 해제(delete)해준 경우에는 다른 포인터는 해제된 공간을 가리키고 있기에 이를 사용하려고 할 때 에러가 발생할 수 있다.
- 상속을 했을 경우에는 Virtual이라는 키워드를 넣어야지 자식의 객체 또한 소멸자를 호출해 메모리 해제할 수 있다.
4. Pointer
1) & 사용하는 방식
- 기존 변수에 & 사용: 주소연산자
- 변수 선언과 정의를 할 때 & 사용: 레퍼런스 선언 및 정의
2) * 사용하는 방식
- 포인터형 변수에 * 사용: 포인터가 가리키는 메모리 주소의 값
- 변수 선언과 정의를 할 때 * 사용: 포인터형 변수 선언 및 정의
3) Null Pointer
- 에러가 발생할 여지가 있는 코드를 짰을 때 쓰레기 값이 들어가있는 것과 Null Pointer가 들어가 있는 것을 구분할 수 있다.
5. Queue
1) Queue란?
(1) 큐의 개념
- FIFO로 먼저 삽입한 데이터를 삭제하는 자료구조이다.
- Circular queue가 효율적이기에 주로 이를 이용해 구현한다.
- 동종 항목 요소 그룹으로 새로운 요소가 한쪽 끝에 추가되고 다른 쪽에서 제거된다.
(2) 우선순위 큐
- 중요도가 높은 것을 먼저 뽑아낼 수 있는 자료 구조
- 우선순위 큐는 가장 앞쪽에 대해서만 우선순위가 높으면 되기에 주로 힙자료구조를 통해 구현한다. 또한 전체 정렬을 위한 알고리즘을 구현할 필요는 없다.
2) 데이터를 삭제할 때 큐 구현 방법
(1) 뒤에 있는 데이터를 모두 앞으로 한 칸씩 옮긴다.
- 연산 횟수가 증가해 부담됨
- 비어있는 것은 Enqueue를 위한 포인터가 -1을 가리키는지 확인해서 구현할 수 있다.
(2) 포인터를 옮겨가며 뽑을 데이터를 가리킨다.
- 이때 Enqueue를 위한 포인터가 -1을 가리키는지를 체크해 큐가 비었는지를 확인할 수 없다. 이에 따라 Circular Queue형태로 구현한다. 이를 위해 RESERVED 칸을 만들어 데이터가 존재하는지, 존재하지 않는지를 확인할 수 있다.
- 이에 따라 포인터가 두 개여야하고, isFull이나 IsEmpty와 같은 메소드가 중요해짐
- RESERVED가 없으면 front와 rear이 같은 경우에 isFull과 IsEmpty를 구분할 수 없다. 이에 따라 RESERVED를 만들어놓고, 효용성을 고려해 앞에 인덱스를 비워둔다. 따라서 데이터의 크기와 연산 속도를 고려할 필요가 있다.
- RESERVED는 front가 가리키고 있는 것으로 데이터가 없는 것을 의미한다.
- 데이터 삽입을 위한 점검: (rear+1) % maxQue == front
- 데이터 삭제를 위한 점검: rear == front
cf) front와 rear를 0으로 한다하더라도 (rear + 1) % maxQue 은 해줘야하므로 연산 속도의 차이는 없다. 또한 이는 O(1)의 시간 복잡도를 가진다.
cf) 초기화를 할 때의 시간복잡도는 대게 O(1)이다.
'강의 내용 정리 > 자료구조' 카테고리의 다른 글
| 자료구조 구현 (1), Unsorted list (0) | 2022.05.11 |
|---|---|
| 자료구조 (6), Linked Structured (0) | 2022.05.02 |
| 자료구조 (4) ADTs Unsorted List and Sorted List (0) | 2022.03.17 |
| 자료구조 (3) 데이터 디자인과 구현 (0) | 2022.03.17 |
| 자료구조 (2) 소프트웨어 공학 원리 (0) | 2022.03.17 |