Study
data-structure
03 Stack and Queue

스택(Stack)

  • 먼저 들어온 데이터가 나중에 나가는 자료구조
  • 새로운 원소를 삭제할 때는 마지막 원소가 삭제된다

스택의 연산

연산시간복잡도설명
1삽입(push)O(1)스택에 원소를 삽입하는 연산
2추출(pop)O(1)스택에서 원소를 추출하는 연산
3최상위 원소(Top)O(1)스택의 최상위 원소(마지막에 들어온 원소)를 확인하는 연산
4EmptyO(1)스택이 비어 있는 지 확인하는 연산

JavaScript에서 스택을 구현하는 방법 - 배열 자료형

  • JavaScript에서 기본적인 배열 자료형은 다음의 두 가지 메서드를 제공한다
    • push() 메서드 : 마지막 위치에서 원소를 삽입하며, 시간 복잡도는 O(1)이다
    • pop() 메서드 : 마지막 위치에서 원소를 추출하며, 시간 복잡도는 O(1)이다
  • 따라서 일반적으로 스택을 구현할 때, JavaScript의 배열(array) 자료형을 사용한다

JavaScript에서 스택을 구현하는 방법 - 연결 리스트

  • 스택을 연결리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다
  • 연결 리스트로 구현할 때는 머리(head)를 가리키는 한 개의 포인터만 가진다
    • 머리(head) : 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터
  • 삽입할 때는 머리 위치에 데이터를 넣는다
  • 삭제할 때는 머리 위치에서 데이터를 꺼낸다

큐(Queue)

  • 먼저 삽입된 데이터가 먼저 추출되는 자료구조
  • 탐색 알고리즘에서 활용도가 높다
  • 머리(head) : 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
  • 꼬리(tail) : 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터

큐 동작 속도 : 배열 vs 연결 리스트

  • 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사용할 때 수행 시간 관점에서 효율적이다
    • 배열
      • enqueue : 새로운 배열을 생성하기 때문에 O(n)의 시간 복잡도를 가진다. 또한 모든 요소를 복사해야 하기 때문에 비효율적이다
      • dequeue : 배열을 복사하고 슬라이싱하는 과정 때문에 O(n)이 소요된다. 요소 하나를 제거할 때마다 모든 배열을 재구성해야 한다
    • 연결 리스트
      • enqueue : 새로운 항목을 딕셔너리의 끝에 추가하는 작업이므로 O(1)이다
      • dequeue : 배열과 달리 요소를 삭제할 때 모든 요소를 이동시키지 않으므로 O(1)이다
  • 그러나, 연결 리스트의 경우 배열보다 코드 가독성이 좋지 못하다는 단점이 존재한다
  • 자바스크립트에서는 Dictionary 자료형을 이용하여 큐를 구현하면 간단하다

스택과 큐 구현하기

스택

class Stack {
  #arr;
 
  constructor(values) {
    this.#arr = values ?? [];
  }
 
  getStack() {
    return this.#arr;
  }
 
  push(el) {
    this.#arr = [...this.#arr, el];
  }
 
  pop() {
    const newArr = [...this.#arr];
    this.#arr = newArr.slice(0, -1);
    return Number(newArr.slice(-1));
  }
}
 
const stack = new Stack();
stack.push(3);
stack.push(5);
console.log(stack.getStack()); // [3, 5]
console.log(stack.pop()); // 5
console.log(stack.getStack()); // [ 3 ]
 
const s2 = new Stack([1, 2]);
console.log(s2.getStack()); // [1, 2]
s2.push(3);
s2.push(5);
console.log(s2.getStack()); // [ 1, 2, 3, 5 ]
console.log(s2.pop()); // 5
console.log(s2.getStack()); // [ 1, 2, 3]

Stack 테스트해보기

현재 Stack: []

큐

배열로 구현해보기

class Queue {
  #arr;
 
  constructor(values) {
    this.#arr = values ?? [];
  }
 
  getQueue() {
    return this.#arr;
  }
 
  enqueue(el) {
    this.#arr = [...this.#arr, el];
  }
 
  dequeue() {
    const newArr = [...this.#arr];
    this.#arr = newArr.slice(1);
    return Number(newArr.slice(0, 1));
  }
}
 
const queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
console.log(queue.getQueue()); // [ 3, 5 ]
console.log(queue.dequeue()); // 3
console.log(queue.getQueue()); // [ 5 ]
 
const q2 = new Queue([1, 2]);
console.log(q2.getQueue()); // [1, 2]
q2.enqueue(3);
q2.enqueue(5);
console.log(q2.getQueue()); // [ 1, 2, 3, 5 ]
console.log(q2.dequeue()); // 1
console.log(q2.getQueue()); // [ 2, 3, 5 ]

Queue 테스트해보기 - 배열

현재 Queue: []

연결 리스트로 구현해보기

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex += 1;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex += 1;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}
 
/** 큐 테스트 */
const queue = new Queue();
 
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.enqueue(5);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(7);
queue.dequeue();
queue.enqueue(1);
queue.enqueue(4);
queue.dequeue();
 
// 먼저 들어온 순서대로 출력
while (queue.getLength() !== 0) {
  console.log(queue.dequeue());
}

Queue 테스트해보기 - 연결 리스트

현재 Queue: {}

확실히 코드 구현에 있어서 배열을 사용하는 것보다 연결 리스트를 사용하는 것이 비교적 복잡하긴 하다.

그래도 시간 복잡도 면에 있어서 훨씬 좋기 때문에, 성능이 중요한 상황에서는 Linked-List를 사용해야 할 것 같다.

02 Array and Linked List04 Tree and Priority Queue