선형 자료 구조

자료구조 및 알고리즘/k-mooc

stop0729 2021. 7. 16. 12:12

배열과 리스트

동적할당 .. 링크 참고

void *malloc(size_t size );

void free(void *memblock );

call by value : 함수의 인자로 들어가는 변수의 값을 복사하여 넘겨주기때문에 해당변수의 값이 수정되지 않는다.

call by reference : 변수의 주소를 넘겨주기때문에 변수의 값이 수정될 수 있다.

linked list

각각의 node(vertex)는 데이터의 값 자체와 다음 next 노드의 포인터를 가지게 된다.

만약 사용 언어가 c라면 구조체, 객체지향 언어라면 겍체에 데이터 필드와 링크 필드를 만든다.

linked list 자체는 첫번째 node인 head와 len 정보를 가지고 있다.

배열의 경우엔 중간 엘리먼트를 추가/삭제할 경우 불편하게 모든 엘리먼토를 손보고 과정이 느렸는데, linked list의 경우 빠르다.

스택

선형 자료구조의 하나. last-in first-out 특성을 가진다.

top은 스택의 최상단.

push : 탑에 스택을 하나 쌓는다.

pop : 탑에서 하나를 뺀다.

어떤 문제에 적용 가능한가? -> 괄호 매칭 문제. 괄호를 여는 문자면 push, 괄호를 닫는 문자면 pop.

스택이 비어있다고 하면 주어진 문자열은 괄호 차원에서 잘 밸런스가 되어있는것.

큐

first-in first-out. 줄을 서는것과 비슷한, 먼저 줄선사람이 먼저 서비스를 받는 특성.

insertion 같은경우 큐의 뒤(rear, back, tail)에서 일어난다.

deletion 같은경우 큐의 앞(head, front)에서 일어난다.

front : 큐의 맨 앞. deletion이 발생

rear : 큐의 맨 뒤. insertion이 발생

Enqueue : rear에 insert

Dequeue : front에서 delete

Enqueue3 상황에서 앞에 2개의 공간이 있음에도 데이터를 rear에 추가할수 없는 상황 발생.

큐를 동그랗게 만들면 해결가능. -> circulat queue

STL : 소프트웨어 패키지. sorting, list, stack, queue 등등다양한 알고리즘 구현 가능.