immersive TIL #3

자료구조(Data Structure)

자료구조를 설명하기에 앞서 자료란 위키백과에 따르면 "문자,소리,숫자,영상,단어 등의 형태로 된 의미 단위, 자료를 의미있게 정리하면 정보가 된다" 쉽게 말해 웬만한건 다 자료가 될 수 있다.

이런 데이터 처리를 연산속도가 엄청나게 빠른 컴퓨터에게 맏긴다면 굉장히 효율적으로 데이터를 사용 할 수있다.

자료구조란 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한것이다.

TMI)
컴퓨터는 0과1만 이해 할 수 있기때문에 천공카드라는것을 사용해 이진수 데이터를 나타내 컴퓨터에게 명령을 내렸다. 그러나 이제 프로그래밍 언어를 만들어서 프로그래밍 언어와 컴퓨터가 사용하는 기계어 사이에 번역기가 등장했는데 그게 바로 컴파일러다

Data Type

• 컴퓨터에 0과1로 저장되어 있는 데이터를 인간이 사용하는 여러가지 데이터들의 종류로 해석하기 위한 장치
• 같은 이진 데이터라도 인간의 해석에 따라 다른 데이터가 될 수있음

Stack

스택은 선형 자료구조로, 맨 끝에 들어간 자료가 처음으로 나오는 선입후출(First In, Last Out: FILO), 후입선출(Last In, First Out: LIFO)의 구조이다.

연결 리스트인데 뒤로 넣고 뒤로만 뺄 수 있다. 앞으로는 넣지도 빼지도 못한다.

하노이 탑의 원리와 같다.

stack의 메소드

1.push(element) - 요소를 스택의 최상단에 추가
2.pop() - 스택의 최상단에서 요소를 제거하고 반환
3.size() - 스택의 현재 요소 개수를 반환

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
    this.count = 0;
  }

  size() {
    if (!this.storage) {
      return 0;
    }
    return Object.keys(this.storage).length;
  }

  push(element) {
    this.storage[this.count] = element;

    return this.count++;
  }

  pop() {
    let data = this.storage[this.count - 1];
    delete this.storage[this.count - 1];
    this.count--;
    return data;
  }
} 

stackTop은 스택의 마지막 요소를 알려준다. 스택의 마지막 요소를 top이라고 부르기도 한다.
this.top이 곧 요소 개수를 의미

stack에서 발생하는 오류 2가지

1. Stack Overflow: 일반적으로 프로그램 시작시 호출되는 스택은 제안된 양의 주소공간을 가지고 시작됩니다. 이때, 프로그램이 이용가능한 공간 이상을 사용하려고 할 때, 즉 스택의 공간이 이미 꽉 차있는데 더 넣으려 할 때 스택 오버플로가 발생합니다.

2. Stack Underflow: 이는 스택 오버플로와 반대의 경우로 스택의 공간이 비어있는데 자료를 빼내려고 하는 등, 범위 이하의 공간에 접근하려고 할 때 발생합니다.

Queue

큐는 선형 자료구조로 놀이공원에서 줄서는 원리와 같다. 제일먼저 들어온 것이 제일 먼저 나간다(FIFO: first in, first out).

큐에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear가 있는데
큐의 원소개수는 맨 마지막 값 다음 위치 - 맨 앞의 위치 (rear - head)를 계산하여 구할 수 있다.

Queue의 메소드

1.enqueue(element) - 요소를 큐의 뒤에 추가
2.dequeue() - 요소를 큐의 앞에서 제거하고 반환
3.size() - 큐의 현재 요소 개수를 반환
추가로 제일 앞의 데이터를 알 수 있는 front가있다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
    this.count = 0;
    this.dequeCnt = 1;
  }

  size() {
    if (!this.storage) {
      return 0;
    }
    return this.count;
  }

  enqueue(element) {
    if (!this.front) {
      this.front = element;
      this.storage[this.count] = element;
    } else {
      this.storage[this.count] = element;
      this.rear = this.storage[this.count];
    }
    return this.count++;
  }

  dequeue() {
    if (!this.front) {
      return 0;
    }
    let data = this.front;
    this.front = this.storage[this.dequeCnt];

    this.dequeCnt++;
    this.count--;
    return data;
  }
}