JS 데이터 구조 스 택 대기 열

5871 단어
창고 구조
  • 스 택 은 선진 후 출 (LIFO) 원칙 에 따 른 질서 있 는 집합 이다.새로 추가 하거나 삭제 할 요 소 는 모두 스 택 의 같은 끝 에 저장 되 어 있 습 니 다. 스 택 지붕 이 라 고 부 르 고 다른 한 끝 은 스 택 바닥 이 라 고 부 릅 니 다. 새로운 요 소 는 스 택 꼭대기 에 가 깝 고 오래된 요 소 는 스 택 바닥 에 가 깝 습 니 다.

    • 창고 의 몇 가지 방법
  • push (element (s)): 스 택 꼭대기 에 하나 또는 몇 개의 새로운 요 소 를 추가 합 니 다
  • pop (): 스 택 꼭대기 의 요 소 를 제거 하고 제 거 된 요소
    • 를 되 돌려 줍 니 다.
  • peek (): 스 택 꼭대기 에 있 는 요 소 를 되 돌려 주 고 스 택 을 수정 하지 않 습 니 다 (이 방법 은 스 택 꼭대기 요 소 를 제거 하지 않 고 되 돌려 줍 니 다)
  • isEmpty (): 스 택 에 요소 가 없 으 면 true 로 돌아 갑 니 다. 그렇지 않 으 면 false
    • 로 돌아 갑 니 다.
  • clear (): 창고 안의 모든 원소 제거
  • size (): 스 택 에 있 는 요소 의 개 수 를 되 돌려 줍 니 다.이 방법 은 배열 의 length 와 유사 하 다
    • 스 택 을 표시 하고 이 방법 을 설명 하기 위해 클래스 를 만 듭 니 다.
    class Stack {
    constructor() {
            this.items = []
        }
        // push          
    push(element) {
            this.items.push(element)
        }
        //        ，          
    pop() {
            return this.items.pop()
        }
        // peek        ，        （             ，     ）
    peek() {
            return this.items[this.items.length - 1]
        }
        // isEmpty              true，     false
    isEmpty() {
            return this.items.length === 0
        }
        // size          ，        length    
    size() {
            return this.items.length
        }
        //clea            ，     
    clear() {
        return this.items = []
    }
}

    Stack 클래스 사용 하기
    우선 Stack 클래스 를 초기 화하 고 요 소 를 추가 해 야 합 니 다. 이 때 스 택 안의 요소 가 비어 있 기 때문에 isEmpty 방법 을 사용 하면 ture 로 돌아 갑 니 다.
    const stack = new Stack()

stack.push('   ')
stack.push('   ')
stack.push('   ')
stack.push('   ')

console.log(stack.items) //         
console.log(stack.pop()) //      （LIFO     ，        ）
console.log(stack.items) //                  
console.log(stack.peek()) //            
console.log(stack.isEmpty())//false
console.log(stack.size())   //3
console.log(stack.clear())//0

    스 택 을 사용 하여 실제 문 제 를 해결 합 니 다 (10 진법 2 진법)
    //     
function dec2bin(num) {
    const stack = new Stack()
    //          while  ， num  0     while  
    while (num > 0) {
        let remainder = num % 2 //    
        num = Math.floor(num / 2) // Math.floor    
        stack.push(remainder); //       
    }
    // console.log(stack.items)    //                    
    let binString = ""
    while (!stack.isEmpty()) {
        binString += stack.pop()
    }

    return binString
}
console.log(dec2bin(100)) //1100100

    대열 구조
  • 대열 은 선진 선 출 (FIFO, 선착순 서비스 라 고도 함) 원칙 을 따 르 는 질서 있 는 방향 이다.대기 열 은 끝 에 새 요 소 를 추가 하고 상단 에서 요 소 를 제거 합 니 다.최근 에 추 가 된 요 소 는 대열 의 끝 에 있어 야 합 니 다
    • 대열 의 몇 가지 방법
  • enqueue (element (s): 대기 열 끝 에 새 항목 을 추가 합 니 다.
  • dequeue (): 대기 열의 첫 번 째 항목 (대기 열의 맨 앞 에 있 는 항목) 을 제거 하고 제 거 된 요 소 를 되 돌려 줍 니 다.
  • peek (): 대기 열 에 있 는 첫 번 째 요 소 를 되 돌려 줍 니 다. 가장 먼저 추가 되 고 가장 먼저 제거 되 는 요소 입 니 다.대기 열 은 아무런 변동 도 하지 않 습 니 다. (요 소 를 제거 하지 않 고 요소 정보 만 되 돌려 줍 니 다. stack 류 의 peek 방법 과 매우 유사 합 니 다.)이 방법 은 다른 언어 에서 도 front 방법 이 라 고 할 수 있다.
  • isEmpty (): 대기 열 에 요소 가 포함 되 어 있 지 않 으 면 true 로 돌아 갑 니 다. 그렇지 않 으 면 false
    • 로 돌아 갑 니 다.
  • size (): 대기 열 에 포 함 된 요소 개 수 를 되 돌려 줍 니 다. 배열 의 length 속성 과 유사 합 니 다
    • 클래스 를 만들어 서 대기 열 을 표시 하고 이 방법 을 설명 합 니 다.
    class Queue {
    constructor() {
        this.items = []
    }
    enqueue(element) {
        this.items.push(element)
    }
    dequeue() {
        return this.items.shift()
    }
    peek() {
        if (this.items.length === 0) return null
        return this.items[0]
    }
    isEmpty() {
        return this.items.length === 0
    }
    size() {
        return this.items.length
    }
}

    queue 클래스 사용 하기
    const queue = new Queue()
queue.enqueue("   ")
queue.enqueue("   ")
queue.enqueue("   ")
queue.enqueue("   ")
console.log(queue.items)
console.log(queue.dequeue())//          
console.log(queue.items)//      
console.log(queue.peek())//

    대기 열 을 사용 하여 실제 문 제 를 해결 하 다.
    북 을 치 며 꽃 을 한 바퀴 돌 고 삼촌 을 시작 합 니 다. 어떤 숫자 를 세 는 사람 이 자동 으로 탈락 하고 마지막 에 남 은 사람 이 승리 합 니 다. 이 사람 은 누구 입 니까?
    //     
function passGame(nameList, num) {
    //     
    const queue = new Queue()
    for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])//nameList    
    }
    //       
    while (queue.size() > 1) {
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())//    3    
        }
        queue.dequeue()//   3    ，  
    }

    return queue.peek()
}
console.log(passGame(["   ", "   ", "   ", "   "], 3))//

    우선 순위 대기 열
  • 쉽게 말 하면 회원 새치기
  • 병원 응급 
    class QueueElement {
  constructor(element, priority) {
      this.element = element
      this.priority = priority
  }
}
class PriorityQueue extends Queue {
  enqueue(element, priority) {
      // 1.  QueueElement  
      const queueElement = new QueueElement(element, priority)
          //          
      if (this.isEmpty()) {
          this.items.push(queueElement)
      } else {
          let added = false
          for (let i = 0; i < this.items.length; i++) {
              if (this.items[i].priority > queueElement.priority) {
                  this.items.splice(i, 0, queueElement)
                  added = true
                  break
              }
          }
          if (!added) {
              this.items.push(queueElement)
          }
      }
  }
}
const queue = new PriorityQueue();
queue.enqueue("aaa", 100)
queue.enqueue("bbb", 150)
queue.enqueue("ccc", 120)
queue.enqueue("ddd", 99)
queue.items.forEach(item => {
  console.log(item.element, item.priority) //       
})
    • 《 큰소리 데이터 구 조 》 노트 - day 2
    better - queue 를 사용 하여 복잡 한 작업 관리

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage