TIL: 2022-11-17

⚙️ 오늘 배운 주제

자료구조 - 스택, 큐

 

🐹 오늘의 기분

섹션 4에 들어왔다. 이번 유닛에서는 자료구조를 배우는데 그 첫 타자는 스택과 큐였다. 독학할 때 파이썬으로 공부해본 적이 있어서 개념 자체는 크게 어렵게 느껴지지 않았다. 자바스크립트 class로 구현해보고 두 자료구조를 응용한 여러 문제를 푸는 것이 어려웠다. 브라우저 스택이랑 박스 포장까지는 페어분과 고민하면서 나름 빠르게 풀었는데 프린터 큐에서 완전 막혀버렸다. 한 시간 정도 고민하다가 결국 레퍼런스를 봤는데 더 이해가 안 됐다 (?) 라이브세션에서 알려주신 코드가 더 이해가 잘 됐다. 올려주신 레퍼런스 보면서 풀이 뜯어보고 혼자 다시 풀어보려고 한다.

 

🗝 키워드

스택, 큐, 후입선출, 선입선출, push, pop, enqueue, dequeue

 

🗣 스스로에게 설명

스택의 구조와 특징

이미지 출처: Javatpoint

후입선출 LIFO

가장 나중에 들어온 요소가 가장 먼저 빠져나간다.

데이터는 하나씩만 들어가고 나올 수 있으며 데이터의 입구와 출구가 같다. (입출력 방향이 같다)
스택은 크기가 제한되어 있어 이를 초과하면 스택오버플로우가 발생할 수 있다.

 

스택에 삽입하는 연산을 push, 마지막 요소를 빼는 연산을 pop이라고 한다.

 

자바스크립트 class로 스택을 구현한다면 아래와 같이 쓸 수 있다.

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

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

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

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

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

    return result;
  }
}

자바스크립트 배열을 스택처럼 쓴다면 배열의 push와 pop 메소드를 이용할 수 있다.

 

큐의 구조와 특징

이미지 출처: csgeek

선입선출 FIFO

가장 먼저 들어온 요소가 가장 먼저 빠져나간다.

스택과 마찬가지로 데이터는 하나씩만 들어가고 나올 수 있다.
큐는 입구와 출구가 따로 마련되어 있다. (입출력 방향이 다르다)

 

큐에 데이터를 삽입하는 연산을 enqueue, 데이터를 빼는 연산을 dequeue라고 한다.

 

큐는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.
대표적인 예로 프린터 큐가 있다.

 

 자바스크립트 class로 큐를 구현한다면 아래와 같이 쓸 수 있다.

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

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

  enqueue(element) {
    this.storage[this.rear] = element;
    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;
  }
}

자바스크립트 배열을 큐처럼 쓴다면 배열의 shift와 push 메소드를 이용할 수 있다.
하지만 배열을 이용하면 shift 연산 수행 시 빈 자리를 메꾸기 위해 나머지 요소들이 한 칸씩 앞으로 이동해야 하므로 O(n)의 시간이 걸린다는 것에 유의해야 한다.

 

❓ 막혔던 부분

코드를 치는 것보다 문제에서 요구하는 바를 이해하고 로직을 생각해내는 것이 더 중요함을 새삼 깨달았다.

문제를 풀다 막힐 때에는 아무리 생각해도 한 가지 방법으로만 생각이 흘러가서 그게 고민이다 ㅠㅠ

 

🔎 공부가 더 필요한 부분

원형 큐 (CIrcular Queue) - 선형 큐의 단점을 보완한 자료구조, 맨 앞과 뒤의 인덱스를 기억하여 선형 배열을 원형인 것처럼 사용하는 자료구조이다. (참고: https://velog.io/@mcc919/Data-Structure-%EC%9B%90%ED%98%95-%ED%81%90Circular-Queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0)