자료구조

자료구조의 개념

자료구조(data structure)는 효울적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

여기서 데이터의 처리를 할때 데이터 사이에 참조 관계에 있어서 선형 구조, 나무 구조,
정보를 지정하는 노드 들이 가장 위에 뿌리 노드를 정점으로 부모,자식,자손 관계를 이루며
나뭇가지처럼 갈라진 구조이다.
가지의 맨 끝에 있는 노드는 리프라고한다.

효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로
사용하면서 연산을 수행하도록 해줍니다.

스택 (Stack)

스택은 제한적으로 접근할 수 있는 나열 구조 입니다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out) -> 입,출구가 일자로된
주차장으로 생각하면 될 것같다.

스크린샷, 2019-07-24 13-29-06.png

네모들이 DATA들이 들어오면 최근에 들어왔던 자료부터 나오게 됩니다. 이렇게 나중에 넣은 값이 먼저 나오는
것을 LIFO 구조라고 합니다.

의사코드 (pseudo code)

    1. object를 새로 만든다.
     2. push로  값을 하나씩 넣어준다.
    3. pop로 맨 뒤에 값을 빼버린다.

 const Stack = function () {
   const someInstance = {};

   const storage = {};
   let count = 0;

   someInstance.push = function(value) {  // value = 'a'
     storage[count] = value;              // storage[0] = 'a'  => { '0' : 'a' } 
     count++;                             // count = 1; 다음에 들어올값의 키가 '1' 로 증가시키기
   }; 

   // pop 에서는 '0' 번째 자리 없으면 undefinded 를 하고, 카운트를 이용해 삭제를 이용합니다.
   someInstance.pop = function() {
     if (!storage['0']) return undefind;  
     let temp = storage[count - 1];
     delete storage[count - 1];
     return temp;      
   }

   // size 크기 확인은 카운트로
  someInstance.size = function() {
    return count;
  }

   return someInstacne;

   stack.push("a");
   stack.push("b");
   stack.push("c");
   stack.pop();  

큐 (Queue)

큐는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In first Out)구조로 저장하는 형식입니다.
먼저 줄선사람이 먼저 나가는 것 입니다.

큐는 put (input) 과 get (delete)을 이용하여 구현됩니다.
front(head)와 rear(tail)는 데이터 위치를 가르킵니다.
** front는 데이터를 get 할 수 있는 위치, rear은 데이터를 put 할 수있는 위치를 의미합니다 (한번 다시 읽어보세요~!!)

예제
게임 대기열 , 프린터 출력

스크린샷, 2019-07-24 13-57-01.png

큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put할 수 없는 경우)를 오버플로우(overflow),

큐가 비어 있어 자료를 꺼낼 수 없는 경우 (get 할 수 없는 경우)를 언더플로우(Underflow)라 합니다.

    1. 빈 객체을 만들어 준다.
    2. 데이터 값을 하나씩 push 해준다.
    3. 데이터의 제일 첫 번재로 들어온 것으 빼려면 shift()로 빼준다.

   const Queue = function () {

     const someInstance = {};
     const storage = {};
     let count = 0;
     let head = 0;
     let tail = 0;

     // en('a') => { '0' : 'a' }
     // en ('b') => { '0' : 'a', '1' : 'b' }
     // de () => {'1' : 'b'}
     someInstance.enqueue = function(value){
     storage[tail] = value;
     count++;
     tail++;
     };

     // 큐에서는 head 를 빼줘야 합니다.
     someInstance.dequeue = function() {
       if (!storage[head]) return undefined;
       let temp = storage[head];
       delete storage[head];
       head++;
       count--;
       return temp;
     };

     someInstance.size = function(){
       return count;
     };
   }

     queue.enqueue("a");
     queue.enqueue("b");
     queue.dequeue();
     queue.enqueue("c");

연결 리스트 (Linked List)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결 되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

  • 연속되는 항목들이 포인터로 연결된다.
  • 마지막 항목은 Null을 가르킨다.
  • 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
  • (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.
  • 메모리 공간을 낭비하지 않는다(하지만 포인터를 위한 추가의 메모리를 필요로 한다.)

배열에 비해 데이터의 추가/ 삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.
즉, 탐색 또는 정렬을 자주 하면 배열을, 추가 / 삭제가 많으면 연결 리스트를 사용하는 것이 유리하다.

노드(Node)

연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드로 구성된다.

re.png

위 그림에서 나누어 져있는데 데이터를 저장할 장소다른 변수를 가리키기 위한 장소가 구분되어 있다.

스크린샷, 2019-07-24 15-21-31.png

둘 이상 일때는 위 그림처럼 된다.

연결 리스트 ADT

  • append(데이터): 리스트의 맨 끝에 데이터를 추가한다.

  • removeAt(위치): 해당 위치에 있는 데이터를 삭제한다.

  • indexOf(데이터): 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다.

  • remove(데이터): 데이터를 삭제한다.

  • insert(위치, 데이터): 해당 위치에 데이터를 삽입한다.

  • isEmpty(): 데이터가 하나도 없다면 true를, 그 외엔 false를 반환한다.

  • size(): 데이터 개수를 반환한다. 배열의 length 프로퍼티와 비슷하다.

트리 구조

트리는 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용됩니다.

  • 노드 (node) - 트리 안에 들어있는 각 항목을 말합니다. (모든 동그라미들)
  • 브런치or엣지 - 노드와 노드 사이르 ㄹ이어주는 것입니다.
  • 디그리 (Degree) - 각 노드에서 뻗어나온 가지의 수 (A = 3, b = 2, c = 1, ....)
  • 자식 노드 (child node) - 노드는 여러 자식 노드를 가질 수 있습니다. ( D의 자식은 H, I, J)
  • 부모 노드 (parent node) - 노드 A가 노드 B를 자식으로 갖고 있다면, 노드 A를 노드 B의 '부모 노드'입니다. ( E, F 의 부모는 B)
  • 뿌리 노드 (root node) - 트리의 가장 상층부에 있는 노드를 말합니다. ( A )
  • 잎 노드 (leaf node) - 자식 노드가 없는 노드 (맨 밑 노드) ( K, L, G, M, I, J )
  • 조상 노드 (ancestor node) - 노드 A의 자식을 따라 내려갔을 대 노드 B에 도달할 수 있다면, 노드 A를
    노드 B의 조상 노드라고 부릅니다. (M의 조상은 H, D, A )
  • 형제 노드 (sibling node) - 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라고 부릅니다. ( H의 형제는 I, J )
  • 깊이( Depth ) - Tree에서 노드가 가질 수 있는 최대의 레벨 ( 깊이는 4 )

스크린샷, 2019-07-24 14-19-21.png

의사코드 (pseudo code)

새로운 Tree {
   Tree 생성자 {}
   node 생성자 {
      data;
      child node 리스트;
      size; //child node 갯수
   }
   빈 트리일 경우{
      root = data
   } 아닐 경우 {
      for 현재 노드의 child 갯수 만큼 search{
         child node를 현재 node로 변환하여 재귀함수 실행
      }
   }
}

참고 문헌

[위너비] https://takeuu.tistory.com/172
[생코] https://opentutorials.org/module/1335/8821
[코딩팩토리] https://coding-factory.tistory.com/231