자료구조

#알고리즘: 특정한 작업을 수행하는 유한한 명령들의 집합을 의미한다.

    -알고리즘의 조건 5가지: 1)입력- 입력자료가 존재해야함.
                                      2)출력- 하나이상의 결과.
                                      3)명확성
                                      4)유한성- 모든 경우에 대하여 한정된 단계를 처리한 후에 끝이 나게 된다. 
                                      5)실제성- 실행가능한 것이어야 한다.

    -프로그램 vs 알고리즘: 프로그램은 알고리즘의 4번째 조건, 즉 유한성이 아니라, 무한한 처리가 가능한
                                     경우가 발생한다. OS라는 프로그램은 시스템파괴(system crashes)를 제외하고는
                                     끝없이 수행가능해야 한다.

#선형리스트(linear list; ordered list)- n이 0보다 크거나 같은 요소들로 구성된 한정된 순서.

    -선형리스트의 종류: 1)stack
                                 2)queue
                                 3)deque
    -스텍: 선형으로 된 리스트에서 모든 입력과 삭제가 한쪽 끝(top)에서만 일어나는 구조.                             
              또한 마지막에 입력한 노드가 제일 먼저 제거되기 때문에 LIFO(last-in first-out)구조라 한다.
              //overflow(스텍의 크기를 벗어나는것)와                                
                underflow(더이상 제거할 노드가 없는 스텍의 제일 밑부분(bottom)을 벗어나는것)를 체크한다.

    -큐: 모든 삽입이 한쪽 끝에서 발생하고 다른 한쪽 끝에서는 삭제만이 가능하도록 만들어 놓은
           선형리스트.  FIFO구조(first-in first-out)
           //스텍에서는 1개 포인터로서 해결가능했지만, 큐에서는 삽입과 삭제를 위한 포인터 2개가
              필요하다.

    -디큐: double-ended queue의 약어로, 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.

#String: 메모리 내에서 연속된 영역에 저장된 일련의 문자들의 집합.

#연결리스트(linked_list)
    : 연결리스트는 임의의 위치에 자료를 삽입하거나 제거할 때 링크 부분의 주소만 변경하면 됨으로
      삽입과 제거가 용이하고, 소요시간을 절약할 수 있다//장점
      but, 접근시간(access time)이 느리고 알고리즘 구현이 복잡하며, 링크 포인터를 사용하므로 
      연결리스트가 같은 크기의 자료저장에 대해 배열보다 기억공간이 많이 필요하다는 단점이 있다.       

#기억 장소관리
    1)static storage management: 주기억 장치의 영역을 일정한 크기로 나누어 관리.
    2)dynamic storage management: 필료한 크기의 영역으로 구분하여 관리.
        //기억공간을 각 프로그램에서 필요한 만큼씩 크게에 맞게 분할하여 사용하는 방법으로, 
          기억장치 이용률이 높아지게 된다. 

          기억장소 요구에 따라 적절한 기억 장소를 할당하려면, 
          사용하지 않고 있는 블록(가용공간, 자유블록)들을 계속해서 관리해야 할 필요가 있으며, 
          가용 기억장소를 리스트 형태의 연결구조를 이용하여 관리할 수 있다.
   
 cf) gorbage collection: 동적 기억 장소 할당을 반복하다 보면 볼 수 없는 작은 공간들이 만들어지는데, 
                                이걸 모아서 하나의 쓸 수 있는 큰 블록으로 다시 구성한다.