2. Data Structure - Stack, Queue

helloworldjavascript.net/pages/282-data-structures.html

큐, 스택, 트리 · JavaScript로 만나는 세상

자료구조란? 데이터를 정리하고, 유용하게 활용할 수 있는지 정의해 놓은 것

 

 

---

Stack

• 먼저 들어간 게 나중에 나오는 First In Last Out or Last In First Out 구조
• 스택에 할당된 공간이 꽉 차면 더 이상 Push 할 수 없다.
• 아래 처럼 재귀 함수 실행 시 사용된다. 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조.

연이은 함수 호출, 스택처럼 메모리에 쌓이는 것을 볼 수 있다.

• stack 구현으로 알아보는 stack(객체 이용)
  

class Stack {
  constructor() {
  //Storage 는 객체 타입이기 때문에, 
  //새로운 데이터들은 {key: value} 형식으로 저장된다. 
    this.storage = {};
    this.top = -1;
  }
  //Storage의 크기는 곧 길이를 의미한다. 
  size() {
    return Object.keys(this.storage).length;
  }
  //새로운 element에는 가장 큰 숫자 키를 부여한다. 
  push(element) {
    this.top++;
    this.storage[this.top] = element;
  }
  //가장 큰 숫자 키를 가진 element부터 삭제한다. 
  //pop 메소드를 사용하면 삭제된 element를 return 한다. 
  pop() {
    if(this.size() === 0){
      this.top = -1;
      return undefined;
    }
    //reference:
    // if (this.size() <= 0) {
    //   return;
    // }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top--;

    return result;
  }
}

---

Queue

 

 

• 먼저 들어간 게 먼저 나오는 First In First Out or Last In Last Out 구조
• 데이터가 나가는 위치는 가장 앞 / 들어오는 위치는 가장 뒤
• 원형 큐 / 우선순위 큐 등의 베리에이션 존재
• 한 번에 하나의 데이터만 처리가 가능
• 어떠한 작업 / 데이터를 순서대로 실행 / 사용하기 위해 대기시킬 때 사용

 

• queue 구현을 통해 알아보는 queue(객체 이용)

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
    //reference:  return this.rear - this.front;
  }
  //추가되는 element들은 증가되는 인덱스(rear++)를 갖는다. 
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }
  //가장 먼저 추가된 element가 삭제되고 front++ 를 통해
  //그 다음 element가 삭제될 타겟이 되도록 한다. 
  dequeue() {
    if(this.size() === 0){
      this.front = this.rear;
      return undefined;
    }
    //reference:
    // if (this.size() === 0) {
    //   return;
    // }
    const deletedVal = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return deletedVal;
  }
}

의문점

: element들을 추가한 후 모두 삭제해주면, front = rear 이긴 하지만 그 value가 0이 아닌데, 문제 없을까?

 

• queue 의 사이즈를 지정하여 구현한 queue

• 원형 queue 구현

• 우선순위 큐 는 다음시간에 알아보자.

(배열을 이용한 stack, queue 구현 참조 : helloworldjavascript.net/pages/282-data-structures.html)