Data Structure: Stack, Queue, Linked list

여기 소개하는 세 가지 자료구조는 모두 선형적인 데이터 구조를 가진다. 길게 쭉 뻗은 소나무처럼 긴~ 테이블을 생각해보자.

🙋🏻‍♀️ Stack 이 뭐예요?

선반 위에 쌓여있는 접시를 떠올리면 쉽다. 마지막에 온 게 가장 먼저 빠진다. (Last In, First Out) 아래 실생활 사례 참고!

1. 프로그래밍 언어의 런타임에서 함수 호출 관리
2. 실행취소(undo)
3. 노래 플레이리스트
4. 인터넷창 뒤로가기
5. TV 이전화면

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    return this.top + 1;
  }

  push(el) {
    this.top += 1;
    this.storage[this.top] = el;
  }

  pop() {
    if (this.size() <= 0) {
      return;
    }

    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    
    return result;
  }
}

🙋🏻‍♀️ Queue 는 뭐예요?

역시 선형적인 데이터 구조를 가지는데, 차이점은 선입선출! 먼저 온 순서대로 빠진다. 은행에서 번호표 뽑고 차례대로 대기하는 것처럼. (First In, First Out)

1. node.js 런타임에서 이벤트 큐
2. 메세지 큐
3. 메세지 브로커
4. Tree 또는 Graph 구조의 데이터 자료 탐색 시 너비우선탐색 (BFS)
5. 키보드 입력

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

  size() {
    return this.rear - this.front;
  }

  enqueue(el) {
    this.storage[this.rear] = el;
    this.rear += 1;
  }

  dequeue() {
    if (this.size() === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

🙋🏻‍♀️ Linked list 는 뭐예요?

연결리스트에서 노드들은 1) 데이터 2) 포인터 로 구성되어 있다. 포인터라 함은 노드A 가 노드B를 가리키고 있다고 보면 된다. 이 포인터를 통해 각 노드들이 연결되어 있다.

1. Singly linked list
   노드가 다음 노드만 가리킬 때. 어릴 때, 앞사람 어깨에 손을 얹고 꼬리물기 게임하던 것 같은 형태를 가진다. 한 사람 한사람이 노드이고, 내가 얹은 손은 포인터! 그래서 포인터가 한 쪽만 가리킨다.

2. Doubly linked list
   노드가 이전 노드와 다음 노드 모두 가리킬 때. 체육 시간인데, 양 옆 사람과 손을 잡고 있다고 생각해보자. 즉 포인터가 양 방향을 가리킨다.

만약 내가 중간에 있는 노드인데 연결리스트 밖으로 빠지고 싶다면, 내가 빠지면서 이전에 있던 친구 손을 내 다음 친구 손과 연결시켜 주기만 하면 된다. 다시 말해, 데이터의 삽입과 삭제가 빈번히 일어날 경우에 강점이 있는 자료 구조다.

파일시스템 관리