[자료구조] 스택, 큐, 이진 탐색이란?

✅ 1. 스택이란?

스택(stack)은 "쌓아 놓은 더미"라는 뜻으로, 후입선출(LIFO) 구조를 가집니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조입니다. 스마트폰에서 "뒤로 가기" 기능이나 "되돌리기(Undo)" 기능에서 자주 사용됩니다.

스택의 구조

• 상단(top): 스택의 입출력이 이루어지는 부분
• 하단(bottom): 스택의 바닥 부분
• 포화 스택(full stack): 더 이상 데이터가 들어갈 수 없는 상태
• 공백 스택(empty stack): 데이터가 없는 상태

스택의 연산

연산기능

top()	스택의 맨 위에 있는 데이터 반환
push()	스택에 데이터 삽입
pop()	스택에서 데이터를 삭제하고 반환
isempty()	스택이 비어 있으면 true, 아니면 false 반환
isfull()	스택이 꽉 차 있으면 true, 아니면 false 반환

스택의 동적 구현 예시

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.length === 0 ? "스택이 비어 있습니다." : this.items.pop();
  }

  peek() {
    return this.items.length === 0 ? "스택이 비어 있습니다." : this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

// 테스트
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(10);
stack.push(15);
console.log(stack.peek()); // 15
console.log(stack.pop()); // 15
console.log(stack.size()); // 2

 

---

✅ 2. 큐란?

큐(queue)는 선입선출(FIFO) 구조를 가진 자료구조로, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 대표적인 예로는 은행의 번호표 시스템이 있습니다.

큐의 연산

연산기능

enqueue()	큐 맨 뒤에 요소 추가
dequeue()	큐 맨 앞 요소 삭제 및 반환
front()	큐의 맨 앞에 있는 요소 반환
rear()	큐의 맨 뒤에 있는 요소 반환
isEmpty()	큐가 비어 있는지 확인

큐의 동적 구현 예시 (배열 사용)

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.length === 0 ? "큐가 비어 있습니다." : this.items.shift();
  }

  front() {
    return this.items.length === 0 ? "큐가 비어 있습니다." : this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

// 테스트
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue(5);
queue.enqueue(10);
queue.enqueue(15);
console.log(queue.front()); // 5
console.log(queue.dequeue()); // 5

---

✅ 3. 이진 탐색이란?

이진 탐색(Binary Search)은 오름차순으로 정렬된 배열에서 절반씩 탐색하여 원하는 값을 찾는 알고리즘입니다. 이 탐색은 반드시 배열이 정렬된 상태여야만 가능합니다.

이진 탐색의 동작 원리

1. 배열의 중간 요소를 선택
2. 목표 값과 중간 값을 비교
3. 목표 값이 더 크면 오른쪽, 작으면 왼쪽을 탐색
4. 반복

이진 탐색 구현 (반복문)

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

// 테스트
const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7)); // 3

 

---