인터뷰에서 중요한 알고리즘 질문 2

[ 배열 & 스택 & 큐 ]

질서를 만들어 주는 자료구조

 

 

#배열(Array)

배열과 리스트(list)는 사용이 비슷하나 차이가 있다.

배열은 index와 value 쌍의 집합니다.

리스트는 value와 다음 주소를 가리키는 값을 담은 쌍의 집합이다.

 

배열은 연속되다 보니 검색에 좋다.

리스트는 연속되지 않아 검색에 불리하다.

 

배열은 정적이므로 크기를 정해줘야 한다.

리스트는 동적이므로 크기를 몰라도 사용이 가능하다.

CALLOC 하면 지정한 만큼 메모리를 동적 할당하고 0으로 초기화한다.

REALLOC 하면 이미 동적 할당된 메모리 크기를 재조정한다.

 

배열과 리스트

 

#스택(Stack)

 

후입선출(LIFO, Last-in First-Out) 구조이다.

사용하는 함수는 Top, Push, Pop이다.

 

return point와 call을 사용하여 프로그램이 함수를 호출하고 복귀하는 과정을 처리한다.

이 과정은 Stack Frame이라는 구조를 생성하여 복귀주소, 지역변수, 매개변수를 관리한다.

 

Top은 스택의 최상위 원소를 가리킨다.

Push는 Top을 증가시킨다.

Pop은 Top을 감소시킨다.

 

MALLOC 으로 할당된 배열을 사용하고

REALLOC 으로 배열의 크기를 증가시킨다.

Top Push Pop

 

#큐(Queue)

선입선출(FIFO, First-In First-Out) 구조이다.

한쪽 끝에서 삽입이 쌓이고, 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다.

 

처음 삽입이 된 곳을 Rear라고 하고

빠져나가는 값이 있는 곳을 Front라고 한다.

선입선출

OS는 작업 큐를 생성하는데 이 큐로 스케쥴링을 진행한다.

이것을 작업 스케쥴링(OS Scheduling)이라고 한다.

이 큐는 시스템에 들어온 순서대로 처리하는 형태이다.

Rear값이 큐의 마지막인 Front에 도달하면 Full이 되는 구조이다.

 

큐가 포화(Full)되면 큐를 재 정렬해야 한다.

방법은 새로운 넉넉한 큐를 생성하고 Front부터 Rear까지 복사하는 것이다.