24.01.18 선형 자료 구조 2

1. 선형 자료 구조

    - 요소가 일렬로 나열되어 있는 자료 구조를 말한다

 

  1) 벡터

       - 동적으로 요소를 할당할 수 있는 동적 배열

       - 컴파일 시점에 개수를 모른다면 사용해야함

       - 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다

       - 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1) 이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고

         삽입하는데 O(n) 의 시간이 걸린다

       - 뒤에서 삽입하는 push_back() 의 경우 O(1) 시간이 걸리는데 벡터의 크기가 증가되는 시간 복잡도가

         amorized 복잡도, 즉 상수시간 복잡도 O(1) 과 유사한 시간 복잡도를 가지기 때문

       - 위의 그림처럼 push_back() 을 한다고 해서 매번 크기가 증가하는 것이 아니라 2의 제곱승 + 1 마다 크기를

          2배로 늘린다

       

  2) 스택

       - 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질 (LIFO Last In First Out) 을 가진 자료구조

       - 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다

       - 삽입 및 삭제에 O(1), 탐색에 O(n) 이 걸린다

 

  3) 큐

       - 먼저 집어넣은 데이터가 먼저 나오는 성질 (FIFO First In First Out) 을 지닌 자료구조

       - 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가짐

       - 삽입 및 삭제에 O(1), 탐색에 O(n) 이 걸림

       - CPU 작업을 기다리는 프로세스, 스레드 행렬 도는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색,

         캐시 등에 사용됨