LIFO 또는 FIFO? 스택/큐 가이드

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

오늘은 두 가지 필수 데이터 구조인 스택과 큐를 살펴보겠습니다. 우리는 이들의 개념과 사용 사례를 자세히 살펴보고 기존 접근 방식과 프로토타입 기반 접근 방식을 모두 사용하여 JavaScript로 구현해 보겠습니다.

---

스택: 후입선출(LIFO)

팬케이크 더미를 상상해 보세요. 맨 위에 마지막으로 얹은 팬케이크가 가장 먼저 먹게 됩니다. 이것이 바로 스택 데이터 구조가 작동하는 방식입니다. 후입선출(LIFO) 원칙을 따릅니다.

주요 작업

• push(item): 스택의 맨 위에 항목을 추가합니다
• pop(): 스택의 맨 위 항목을 제거합니다
• peek(): 최상위 항목을 제거하지 않고 반환
• isEmpty(): 스택이 비어 있는지 확인

사용 사례

스택은 다음과 같은 시나리오에서 특히 유용합니다.

• 재귀 알고리즘
• 텍스트 편집기의 실행 취소 메커니즘

자바스크립트 구현

클래식 OOP

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

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

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

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

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

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

프로토타입 기반

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

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

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

Stack.prototype.size = function() {
  return this.items.length;
};

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

---

대기열: 선입선출(FIFO)

이제 초점을 대기열로 옮겨 보겠습니다. 스택과 달리 큐는 선입선출(FIFO) 원칙을 따릅니다. 콘서트장의 줄을 생각해 보세요. 먼저 도착한 사람이 가장 먼저 입장합니다.

주요 작업

• enqueue(item): 대기열 끝에 항목을 추가합니다
• dequeue(): 대기열에서 첫 번째 항목을 제거합니다
• peek(): 첫 번째 항목을 제거하지 않고 반환
• isEmpty(): 대기열이 비어 있는지 확인

사용 사례

대기열은 일반적으로 다음에서 사용됩니다.

• 폭 우선 검색 알고리즘
• 작업 예약

자바스크립트 구현

클래식 OOP

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

프로토타입 기반

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

성능 분석

스택과 큐 모두 $O(1)$O(1) 효율적으로 구현 시 핵심 작업(스택의 푸시/팝, 대기열의 대기열 추가/대기 해제)에 대한 시간 복잡성이 줄어듭니다. 따라서 특정 사용 사례에 대한 성능이 뛰어납니다.

두 가지 모두 일반적인 프로그래밍 문제에 대한 우아한 솔루션을 제공하고 보다 복잡한 데이터 구조와 알고리즘의 기초를 형성합니다. JavaScript에서 이러한 구조를 이해하고 구현함으로써 광범위한 Leetcode/알고리즘 문제를 해결할 수 있는 준비를 갖추게 됩니다.

위 내용은 LIFO 또는 FIFO? 스택/큐 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!