LIFO 또는 FIFO? 스택/큐 가이드-JS 튜토리얼-php.cn

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

WBOY

풀어 주다： 2024-08-21 06:13:06

원래의

1140명이 탐색했습니다.

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;
};

로그인 후 복사