자료구조

여러 데이터의 묶음을 어떻게 저장할 것이고, 사용할 것인지 정의한 것이다.

Data

자료구조에서 가장 큰 비중을 차지하는 자료
문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 것들을 자료(data)라고 한다.
자료들이 잘 분석이 되고, 정리되고 활용되어야만 의미가 있다고 볼 수 있다.
무분별하게 마구잡이로 자료를 한 군데, 혹은 여러 군데에 체계없이 저장하거나 하나의 구조로만 정리하고 활용하는 것보다 훨씬 좋기 때문이다.
무수한 상황들을 효율적으로 대응할 수 있는 여러 방법을 연구했다.

• 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법이 무엇이 있을까?
• 웹 브라우저에서 뒤로/앞으로 가는 방법은 무엇이 있을까?
• 게임 매칭을 잡을 때, 수많은 사람들을 통제하는 방법이 무엇이 있을까?
  
  각각의 방안을 모두 모아 자료구조라는 이름이 붙여졌다.
  이 방법 중 가장 많이 쓰이고, 코딩 테스트에 자주 등장하는 네 가지는 Stack, Queue, Tree, Graph 가 있다.
  대부분의 자료구조는 특정한 상황에 문제를 해결하는 데에 특화되어 있다.

Stack

자료(data)를 쌓는 자료구조이다.

예시

골목을 Stack 자료구조, 자동차는 자료(data)로 비유할 수 있다.

가장 먼저 들어간 자동차는 가장 나중에 나올 수 있다.
이처럼 Stack 자료구조의 특성은 입출이 하나인 제한적 접근이 있다.
이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라 부른다.

Stack의 실사용 예제

브라우저에서 뒤로 가기, 앞으로 가기 기능 구현할 때 Stack 자료구조가 활용된다.

1. 새로운 페이지로 접속할 때 현재 페이지를 Prev Stack에 보관한다.
2. 뒤로가기 버튼을 눌러 이전 페이지로 돌아갈 때는 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

Stack 주요 연산

• top(): 스택의 가장 윗 데이터를 반환한다.(제거 하지는 않고 내용만 확인)
• push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에 메모리를 생성, 데이터를 넣는다.
• pop(): 스택의 가장 윗 데이터를 삭제한다.
• imEmpty(): 원소가 있으면 false, 있으면 true를 반환한다.
• createStack(): 공백 슽책을 생성하는 연산
• peak(): 스택의 가장 위 원소를 반환하는 연산(제거하지는 않고 내용만 확인)
• size(): 스택의 요소의 개수를 확인한다.

class Stack {
  constructor() {
    this.storage = {}; // 빈 객체에 스택을 담는다.
    this.top = 0;
  }
  size() {
    return this.top; // 스택의 사이즈
  }
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  pop() {
    if(this.top > 0) {
      const result = this.storage[this.top - 1];
      delete this.storage[this.top - 1];
      this.top--
      return result;
    }
  }
}

Queue

Stack과 반대되는 개념으로, 먼저 들어간 자료(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특성을 가지고 있는 자료구조이다.

예시

톨게이트를 Queue 자료구조, 자동차는 자료(data)로 비유할 수 있다.

가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 빠져나온다.
가장 나중에 진입한 자동차는 앞 자동차들이 모두 빠져나가기 전까지 톨게이트를 빠져나갈 수 없다.

Queue의 실사용 예제

Queue 자료구조는 컴퓨터에서도 광범위하게 활용된다.
컴퓨터와 연결된 프린터에서 인쇄를 할 때
1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서를 인쇄 작업 (임시 기억 장치) Queue에 들어간다.
2. 프린터는 인쇄 작업 Queue로 들어온 순서대로 문서를 인쇄한다.

컴퓨터 장치들 사이에서 (위 예제에서는 컴퓨터와 프린터 사이) 자료(data)를 주고 받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 Queue가 사용된다.
이를 통틀어 버퍼(buffer)라고 한다.

Queue의 주요 연산

• createQueue(): 공백 큐를 생성하는 연산
• isEmpty(): 큐가 공백인지 확인하는 연산, 공백이면 true 아니면 false
• enQueue(): 큐의 rear(맨 뒤)에 원소를 삽입하는 연산
• deQueue(): 큐의 front에 원소를 삭제하는 연산
• peak(): 큐의 front에 있는 원소를 반환하는 연산

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear  = 0;
  }
  size() {
    return this.rear - this.front;
  }
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++
  }
  dequeue() {
    if(this.front < this.rear) {
      const result = this.storage[this.front];
      delete this.storage[this.front];
      this.front++
      return result;
    }else {
      return this.storage;
    }
  }
}

버퍼링(Buffering)의 개념

대부분 컴퓨터 장치에서 발생하는 이벤트는 아래 이미지 오른쪽 파동 그래프와 같이 시간에 따라 불규칙적으로 발생한다.
이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다.
이 둘의 속도 차이를 버퍼(buffer)를 사용하여 해결할 수 있다.

컴퓨터와 프린터 사이의 자료(data)를 사디 한번 생각해보자.
보통 프린터는 속도가 느리고, 상대적으로 CPU는 속도가 빠르다.
CPU는 빠른 속도로 인쇄 자료(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
프린터는 인쇄 작업 Queue에서 자료(data)를 가져가서 일정한 속도로 인쇄한다.
다른 예로, 유튜브 시청을 할 때의 버퍼링은 다운로드된 자료(data)가 영상을 재생하기에 충분하지 않다면 순서대로 Queue에 모아 두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생한다.