면접 준비: 데이터 구조: 창고

너는 나와 마찬가지로 기술 면접을 위해 읽기 자료를 준비하고 있니?기술 면접관이 나에게 말한 것처럼, "기술 면접은 갈수록 어려워진다. 몇 년 전, 우리는 단지 너에게 문자열을 반전시키라고 요구했을 뿐이다. 지금은 데이터 구조와 알고리즘을 잘 해야 한다.*
나는 이전에 두 부분으로 구성된 문장을 썼는데, 첫 번째 문장은 유니버설 데이터 구조: 체인 테이블
다음은 링크입니다.
오늘 우리는 다음 체인 테이블과 공공 그룹에서 발생하는 데이터 구조인 창고를 연구할 것이다.

무엇이 창고입니까?


가장 간단한 방법은 접시에 부침개 한 무더기를 상상하는 것이다.요리사가 다른 부침개를 창고에 추가하려고 할 때, 새 부침개는 창고의 맨 위에만 추가할 수 있다.잠시 후, 요리사가 이 부침개들을 제공할 준비가 되었을 때, 그들은 꼭대기에서 부침개를 찾을 수밖에 없었다.
다시 말하면 먼저 부침개 더미 위에 놓인 모든 물건은 결국 사라진다는 것이다.부침개 창고는 다음과 같은 조건하에서 운행한다
FILO 시스템(먼저 제공).
인코딩을 시작하기 전에 부침개 창고에 대해 다른 관찰을 해 봅시다.
  • 당신이 진정으로 볼 수 있거나 훔쳐볼 수 있는 유일한 부침개는 이 부침개 더미 중 가장 위에 있는 것이다.
  • 우리가 부침개 더미를 방문할 수 있는 유일한 방법은 맨 위의 부침개를 다시 통과하는 것이다!우리는 맨 위에 있는 부침개를 제거할 수 있다. 부침개는 밑에 있는 것을 드러내고, 새로 나온 부침개를 제거하고, 우리가 우리의 점성 접시에 도착할 때까지 밑에 있는 것을 얻을 수 있다.
  • 우리가 창고에 쌓아 놓은 부침개는 순서를 알 것이다. 왜냐하면 부침개마다 그 밑에 있는 하나를 가리키기 때문이다.
  • 우리가 할 수 있는 또 다른 두 가지 일은 창고에 몇 개의 부침개가 있는지 알고 접시에 부침개가 있는지 설명하는 것이다. 즉, (is Empty?).
  • 코드 가져오기


    체인 테이블을 설정하는 방식과 유사하게 우리의 창고는 두 가지 종류가 필요합니다.
    1) "Node"라는 클래스로 스택에 들어갈 정보 노드를 만듭니다.노드는 우리의 부침개다!
    2) "Stack"클래스가 필요합니다. 이 클래스에서는 스택을 조작하는 방법을 작성합니다.
    이것은 지금까지 우리의 골격이다.
    // class “node” to create the nodes, or “pancakes” that
    // will go into our stack:
    
    class StackNode {
      constructor( data, next){
         this.data = data
         this.next = next
      }
    }
    
    // Here’s our class where we’ll keep the methods we need
    // to manipulate our stack.
    // To start each new stack, we’ll begin with a “blank slate”
    //  so we’ll set both the “top” (top pancake) and the length
    //  of the stack to “null”.
    
    class LinkedStack {
      constructor() {
        this.top = null
        this.size = null
      }
      // methods for our stack will go here
    }
    
    
    우리가 계속할 수 있도록 간단한 방법을 추가하기 시작합시다.창고가 비어 있는지 확인하는 방법이 필요합니다. (isEmpty) 창고의 현재 길이 (getLength) 를 가져오고 부침개 (peek) 를 보십시오.
    나에게 있어서 우리가 해야 할 일은 꼭대기가 있는지 없는지를 보는 것이다.우리는 볼 값을 이 표현식으로 되돌려주어서 이 점을 실현할 수 있다.맨 위 = = = 비어 있음
    getLength에 대해 구조 함수에서 시작된 size 속성만 되돌려줍니다.
    peek에 대해 우리의 구조 함수는 우리에게 "top"속성을 제공하기 때문에 우리는 이 속성의 데이터를 되돌려주기만 하면 peek를 진행할 수 있다.
    isEmpty (), getLength (), peek () 메서드를 추가한 후 코드를 살펴보겠습니다.
    class StackNode {
      constructor( data, next){
         this.data = data
         this.next = next
      }
    }
    
    class LinkedStack {
      constructor() {
        this.top = null
        this.size = null
      }
    
      isEmpty(){
        return this.top === null
      }
    
      getLength() {
         return this.size
      }
    
      peek() {
        return this.top.data
      }
    
    }
    
    됐어, 이렇게 많이 했어!이제 이 그림을 보고 어떤 두 가지 방법이 창고 실현의 주요 부분을 구성할지 찾아보자.다음 그림을 살펴보겠습니다.

    위의 그림 왼쪽에서부터 우리는 빈 창고를 보았다.노드를 추가하려면 밀기 방법이 필요합니다.노드를 삭제하려면 "pop"방법이 필요합니다. (JavaScript의 정규 그룹을 떠올리게 합니까?)
    한 번에 한 가지 방법을 만들어 봅시다.

    밀어넣기 ()


    "밀어내기"방법을 작성하려면 다음과 같은 작업을 해야 합니다.
  • 이 방법은 매개 변수로 값을 가져옵니다.이 값은 스택에 전송될 새 노드의 데이터입니다
  • 방법체에서 우리는'stack'클래스를 빌려 새로운 노드를 만들고 파라미터를 이 새 노드에 전달할 것이다.
  • 현재 우리는 새 노드의'next'속성을 현재 맨 위 노드로 설정하고 싶습니다.다시 말하면, 우리는 새로운 노드가 현재의 꼭대기를 가리키기를 바란다.
  • 스택 상단을 새 노드로 재설정합니다.
  • 우리가 방금 창고에서 밀어낸 추가 노드를 설명하기 위해size 속성에 추가합니다.
  • push(value) {    //pass in the value for the new node
      let node = new StackNode(value)    // create a new node
     node.next = this.top   // Our new node will point to the  
                                       //  current top node
     this.top = node          // our new node is now set as the top  
                                       //node     
     this.size ++               // increment size by one                           
    }    
    
    
    우리의 다음 방법: pop()

    pop()


    팝에 대해 우리는 맨 위 노드를 삭제해야 한다.다음은 우리가 어떻게 이 점을 할 것인가이다.
  • 우선 함수 끝에 튀어나온 내용을 되돌려 주기 위해 맨 위 노드를 변수에 저장합니다.
  • 현재 위쪽을 가져와 아래쪽 노드로 설정합니다.
  • 크기를 1로 줄여 방금 튀어나온 노드를 설명합니다.
  • 팝업된 노드에 저장된 데이터를 되돌려줍니다.
  • 다음은 pop () 코드입니다.
    pop(){
      let poppedNode = this.top   // save the 
                              //node we’ll pop to          
                              // a variable
    
     this.top = this.top.next    // set the top 
                               //node to be the 
                               // one below it
    
     return poppedNode.data    // return the data
                            // that was contained
                            // in the poppedNode. 
    }
    
    
    
    이제 LinkedStack 클래스에 다시 써야 하는 방법을 살펴보겠습니다.
    class StackNode {
      constructor( data, next){
         this.data = data
         this.next = next
      }
    }
    
    class LinkedStack {
      constructor() {
        this.top = null
        this.size = null
      }
    
      isEmpty(){
        return this.top === null
      }
    
    
      getLength() {
         return this.size
      }
    
    
    
    
    
    
      push(value) {    
    
        let node = new StackNode(value)   
        node.next = this.top                               
        this.top = node                                           
        this.size ++                                         
     }    
    
      pop(){
        let poppedNode = this.top                                                   
        this.top = this.top.next                                                         
        return poppedNode.data                                            
      }
    
    }
    
    
    
    이것이 바로 기본 창고 데이터 구조의 실현이다.다음은 창고와 관련된 흔한 알고리즘을 살펴보자.
    이와 동시에
    계속 당신의 꿈을 인코딩하세요!
    나마스트,
    탕니
    *한 면접관이 나에게 달성해야 할 기준을 주었다. 중난도 문제를 풀 수 있다Leet Code.고난도의 문제는 거의 묻지 않는다.그는 또 리코드가 너무 어려우면Hacker Rank부터 시작하는 것이 리코드보다 쉽다고 지적했다.

    좋은 웹페이지 즐겨찾기