이번 학기 졸업을 앞둔 학기여서 많은 학점이 남아있지 않기도 했고, 갑작스럽게 이 쪽 공부를 하다보니 이론적인 부분보다 실제 코드를 구현하는 것에 초점을 맞춰 공부를 했었는데 이론적 토대를 공부해보고 싶다는 생각에 컴퓨터 과학 입문을 학교에서 수강하고 있는데요 이번주가 퀴즈였어서 관련 공부들을 조금 정리해보려고 합니다!
어쩌다 보니 자꾸 시험 공부하는 것을 정리하는 느낌이긴 하네요 ㅎㅎ
Data Abstraction
Single Dimensional Array : 첫 번째 값의 위치가 x라고 한다면 i번째 값의 위치는 x + (i - 1) 에 위치하게 되는 형태의 array
Two Dimensional Arrays : row major와 column major가 존재. 여러 행과 열을 가지는 형태의 array를 구현
Contiguous List : 순서가 있는 item의 집합으로 나타남. 가장 간단한 구조의 list
Linked List : contiguous list의 단점을 보완한 dynamic한 list
그림에서처럼 linked list의 경우 contiguous list보다 데이터의 삽입과 삭제가 용이하다.
stack : 삽입과 추출이 같은 end에서 이뤄지는 구조. Last In Firt Out 구조이다. 삽입과 추출이 이루어지는 end를 top이라고 칭하고 데이터의 삽입은 push, 데이터의 추출은 pop이라고 부른다.
push -> stack이 full인지 확인 가능
pop -> stack이 empty인지 확인 가능
queue : 삽입과 추출이 다른 end에서 이뤄지는 구조. Firt in First Out 구조이다. 추출이 이뤄지는 end를 head, 삽입이 이뤄지는 end를 tail이라고 칭한다.
linear queue가 실행되는 구조.
데이터가 추출되면서 head가 한칸씩 밀리게 되고 head앞의 빈 공간을 이용하지 못한다는 측면에서 비효율적이라는 단점이 있다.
linear queue의 비효율성을 해결할 수 있는 방안 중 하나로 circular queue의 적용을 들 수 있다.
