🎯 스택(Stack)

스택은 쉽게 생각하면 박스에 물건을 차곡차곡 정리하는 형태이다. 먼저 들어간 것이 밑에 위치하기 때문에 나중에 나오게 되고, 나중에 들어간 것이 맨 위에 위치하기 때문에 먼저 나오는 형태의 자료구조이다. 때문에 스택의 모든 연산은 스택의 최상단에서 일어난다. LIFO(Last In First Out)

스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용된다.

스택 구현 코드 (JS)

class Stack {
  constructor() {
    this.arr = [];
  }

  push(item) {
    this.arr.push(item);
  }

  pop(item) {
    return this.arr.pop();
  }

  peek() {
    return this.arr[this.arr.length - 1];
  }
}

스택 시간복잡도

  • push: O(1)
  • pop: O(1)

🎯 큐(Queue)

큐는 대기 줄을 생각하면 이해가 쉽다. 대기 줄에서는 먼저 들어온 사람이 먼저 나가듯 큐에서도 먼저 들어온 데이터가 먼저 나가고 나중에 들어온 데이터가 나중에 나가는 형태의 자료구조이다. 데이터의 삽입과 삭제가 큐의 양끝에서 각각 일어나므로 큐의 앞과 뒤를 명확하게 구분지을 필요가 있다. FIFO(First In First Out)

큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

큐 구현 코드 (JS)

class Queue {
  constructor() {
    this.arr = [];
  }

  enqueue(item) {
    this.arr.push(item);
  }

  dequeue(item) {
    return this.arr.shift();
  }
}

큐 시간복잡도

  • push: O(1)
  • shift: O(N)

🎯 덱(Deque)

덱은 Double Ended Queue의 약자로 큐의 양 끝이 front이면서 rear인 형태의 자료구조이다. 이 말은 큐처럼 한쪽에서만 데이터가 들어오고 한쪽으로만 데이터가 나가는 것이 아닌 양쪽 끝에서 데이터의 삭제와 삽입 모두 가능한 것이다.

덱은 스케줄링이 복잡할수록 큐와 스택보다 더 나은 효율을 보여준다.

덱 구현 코드 (JS)

shift 와 unshift 를 사용한다면 쉽게 구현할 것이라고 생각하지만 자바스크립트에서 shift 연산자의 시간복잡도는 O(N)이기 때문에 사용하지 않는 것을 선호한다.

shift 메서드는 0번째 위치의 요소를 제거하고 연이은 나머지 값들의 위치를 한칸씩 앞으로 당기기 때문에 시간복잡도가 O(N)이다. - MDN

class Dequeue {
  constructor() {
    this.arr = [];
    this.front = 0;
    this.rear = 0;
  }

  pushFront(item){
    if(this.arr[0]) {
      for(let i=this.arr.length; i>0; i--) {
        this.arr[i] = this.arr[i - 1];
      }
    }
    this.arr[this.front] = item;
    this.rear += 1;
  }

  pushBack(item) {
    this.arr[this.rear++] = item;
  }

  popFront() {
    const result = this.front >= this.rear ? null : this.arr[this.front++];
    return result;
  }

  popBack() {
    const result = this.head >= this.rear ? null : this.arr[--this.rear];
    return result;
  }