스택, 큐 (Stack, Queue)

자료구조 중 스택과 큐를 다루어 보겠습니다.

우선 스택부터 설명해 볼게요.

스택

블록을 아래에서 부터 위로 쌓아 올리는 구조를 가지고 있습니다. 가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 됩니다.

이러한 자료구조의 특성을 LIFO(Last-in, First-out)라고 합니다.

스택 용어

(1) 삽입 (Push) : Push는 스택의 구조상 최상 위에 데이터가 저장 됩니다.

(2) 삭제 (Pop) : Push와 반대로 데이터를 삭제하는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 최상위 데이터 위치에서 삭제가 됩니다.

(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.

스택 구현

class Stack {
  constructor() {
    this.arr = [];
  }
  push(item) {
    this.arr.push(item);
  }
  pop() {
    return this.arr.pop();
  }
  peek() {
    return this.arr[this.arr.length - 1];
  }
}

const stack = new Stack();

스택 시간복잡도 Big O

• Insertion O(1)
• Deletion O(1)
• Search O(n)

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.

큐

큐는 스택보다 일상에서 더 이해하기 쉬운 개념인데요. 가장 앞에 줄을 선 사람이 먼저 서비스를 받게 되는 것이라 생각하면 이해하기 쉽습니다.

이러한 자료구조의 특성을 FIFO(First-in, First-out)라고 합니다.

큐 용어

(1) Enqueue : 큐 맨 뒤에 데이터 추가

(2) Dequeue : 큐 맨 앞쪽의 데이터 삭제

큐 구현

class Queue {
  constructor() {
    this.arr = [];
  }
  enqueue(item) {
    this.arr.push(item);
  }
  dequeue() {
    return this.arr.shift();
  }
}

const queue = new Queue();

큐 시간복잡도 Big O

• Insertion O(1)
• Deletion O(1)
• Search O(n)

참고
https://helloworldjavascript.net/pages/282-data-structures.html