알고리즘 - 자료구조 (배열/리스트/스택/큐)

자료구조

1. 배열/리스트
   1. 배열
      • 연속공간에 값이 채워져있는 형태
      • 자바의 배열은 값의 추가 및 삭제가 자유롭지않다, size를 선언할때 한번 fix하고나면 수정안됨
      • 인덱스를 통해서 값을 접근하기 용이하다.
      • 배열의 사용법 
   2. 리스트
      • 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 구조 / 가변형
      • 인덱스가 없으므로 값에 접근 하려면 순서대로 접근해야 해서 값에 저 ㅂ근하는 속도가 느림
      • 데이터 삽입 삭제가 빠르다
      • 선언할때 크기를 별도로 지정하지 않아도 된다.
      • arraylist, linkedlist, vector, stack
      •  
   3. 구간합 : 값을 일일히 하나씩 따져서 연산할 떄보다 값의 합을 이용해서 풀면 시간복잡도를 줄일 수있음.
2. 스택/큐
   1. 스택
      1. 마지막에 들어온애가 젤먼저 나가는 구조
      2. 수식계산, 수식괄호검사
      3. 사용방법
   2. 큐
      1. 먼저 넣는 값(front)이 먼저나오고 나중에 나오는 값(rear)이 나중에 나오는 구조
      2. 최근사용문서, 인쇄작업 대기목록, 버퍼
      3. 사용방법
      4. 우선 순위 큐도 있음 : 힙 자료 구조를 이용하여함.
         
         1. 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조.