[알고리즘과 자료구조] 02. 선형 자료구조
내용 정리
오늘은 linear 자료구조 몇 가지와 이를 이용한 코드 몇 개를 살펴보았다.
코드와 함께 call by value와 call by reference등 개념도 배웠다.
array
int scrore[10];위 문장을 이용해 정적으로 array를 할당할 수 있다.
data type, array name, array size가 필요하다.
그렇게 하면 index순으로 연속적인 memory공간이 할당된다.
한편 아래와 같이 동적으로도 array를 할당할 수 있다.
int *score = new int [10];저기서 star(*)를 dereference operator라고 하는데 한국어로 '역으로 참조된 연산자', 즉 '포인터 연산자'라고 한다.
저렇게 주소값을 참조하여 할당하면 배열의 길이 등을 조절할 수 있는 동적할당이 된다.
참고로 &가 reference oprator로 주소값 자체를 나타내는 연산자, 한국어로 '참조 연산자'라고 한다.
delete[] score;더하여 위와 같이 쓰면 할당한 momory공간을 OS에 다시 돌려줄 수 있다.
Linked Lists
모든 element들이 다음 element를 pointing하는 구조.
값을 표시하는 box와 다음 elemnet의 주소를 가르키는 arrorw로 이루어진 구조며
선언할 때에는 element의 개수 len과 시작점 주소 head를 선언해야 한다.
Stack
LIFO, Last in First out
operation은 top부분에서만 이루어지고 값을 넣는 것을 push, 빼는 것을 pop이라 함.
Queue
FIFO, First in First out
값이 들어올 때는(enqueue, insertion할 때는) 뒤쪽(rear, tail, back)으로 들어온다.
값이 나갈 때는 (dequeue, deletion할 때는) 앞쪽(front, head)로 나간다.
이 때 위 그림과 같이 값이 나가고 들어갈 때 front와 rear가 가르키는 주소는 당겨지지 않는다.
따라서 우리는 분명 남는 공간이 있음에도 사용할 수 없는 손해를 본다.
이에 일정 간격으로 원형 구조를 사용한 것이 아래 circular queue다.
나머지 연산자를 활용하여 논리적으로 원형이 된 것이며 이 또한 linear구조로 본다.
STL
standard Templete Library의 약자로 C++의 소프트웨어 패키지 라이브러리다.
여기에는 stack과 queue같은 컨테이너, 그리고 sort와 binary search같은 알고리즘이 포함되어 있다.
여기서 컨테이너란 자료를 담을 수 있는 공간을 말한다.
2주차 수강 후기
아직까지 모르는 내용은 없지만 palndrome check등 예제는 처음 봐서 재밌다.
stack과 queue처럼 여기저기서 배웠지만 제대로 설명은 못하는 개념을 복습하고 있다.