자주 사용하게 되는 알고리즘에 대해서 하나씩 알아보겠습니다.

스택 그리고 큐

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 합니다.

이 포스팅에서는 널리 사용되는 ADT인 큐, 스택에 대해 알아보겠습니다.

스택(Stack)

스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조입니다.
즉, 스택에 마지막으로 추가된 요소가 가장 먼저 나오는 요소입니다.

주요 작동 방식

• push : 스택 맨 위에 요소를 추가합니다.
• pop : 스택에서 최상위 요소를 제거하고 반환합니다.
• peek/top : 스택의 최상위 요소를 제거하지 않고 반환합니다.

자바스크립트에는 내장된 스택 데이터 구조가 없지만 배열을 아주 쉽게 스택으로 사용할 수 있습니다.

let stack = [];
stack.push(1);    // [1]
stack.push(2);    // [1, 2]
stack.push(3);    // [1, 2, 3]

let top = stack[stack.length - 1]; // 3

let poppedValue = stack.pop();  // 3 -> stack is now [1, 2]

큐(Queue)

큐는 FIFO(First In First Out) 원칙을 따르는 선형 데이터 구조입니다.
즉, 큐에 추가된 첫 번째 요소가 가장 먼저 제거됩니다.

주요 작동 방식

• enqueue : 대기열 끝에 요소를 추가합니다.
• dequeue : 대기열에서 맨 앞의 요소를 제거하고 반환합니다.
• front : 대기열의 맨 앞 요소를 제거하지 않고 반환합니다.

JavaScript에서 대기열에 배열을 사용하는 것은 가능하지만 shift (앞에서 요소를 대기열에서 빼기)는 시간 복잡성 측면에서 비용이 많이 드는 작업이기 때문에 최적이 아닙니다.

let queue = [];
queue.push(1);     // [1]
queue.push(2);     // [1, 2]
queue.push(3);     // [1, 2, 3]

let front = queue[0];  // 1

let dequeuedValue = queue.shift();  // 1 -> queue is now [2, 3]

스택 VS 큐

• 기능
  • 스택은 LIFO(후입선출)이고 큐는 FIFO(선입선출)입니다.
• 사용 사례
  • 스택은 함수 호출 스택, 표현식 구문 분석, 역추적 알고리즘과 같은 시나리오에서 자주 사용됩니다.
  • 큐는 주문 처리, 작업 예약, 처리 공정성이 요구되는 시나리오 등에서 사용됩니다.
• 배열 성능
  • 스택의 경우, 끝에서 추가/제거(push 및 pop 사용)가 빠르기 때문에 자바스크립트에서 배열을 사용하는 것이 효율적입니다.
  • 큐의 경우 shift 연산으로 인해 배열을 사용하는 것이 비효율적일 수 있습니다.