2. Data Structure - stack, queue

whljm1003·2020년 11월 14일
1

algorithm

목록 보기
1/1
post-thumbnail

immersive에 탑승하고 벌써 2번째 과제인 Data Structure를 시작했다.
자료구조에서 그나마 수훨하게 진행했던 stack과 queue에 대해 까먹기 전에 리뷰를 남겨야 겠다.

stack

ex)접시

스택(Stack)는 LIFO(Last In First Out) 구조이다.
즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거된다.
조금 더 쉽게 설명해서 식당에서 접시를 생각해보자.
접시는 기둥처럼 쌓이고 다시 사용할 땐 위에꺼를 꺼내서 사용한다.
이것이 stack이다.

# stack의 method
push(element) - 요소를 스택의 최상단에 추가합니다.
pop() - 스택의 최상단에서 요소를 제거하고 반환합니다.
size() - 스택의 현재 요소 개수를 반환합니다.


간단한 pop,push가 가능하고 size가 나타나는 코드를 작성해보았다.

class Stack {
  constructor() {
    this.storage = {}; // {el}
    this.top = 0;
  }

  size() {
    return this.top
  } // push or pop 을 할 경우 최종적인 결과값을 담는다.

  push(element) {
    this.storage[this.top + 1] = element
    this.top = this.top + 1
  } // stack의 맨위에 담는 것

  pop() {
    let result = this.storage[this.top]
     if(this.top === 0){
      this.top = 0 // 제거한다 ex) 1,2 ... 10 / 10을 pop을 하면 10을 제거 
    }
    else {
      delete this.storage[this.top]
      this.top = this.top - 1
    }
    return result 
  }
}

queue

ex) 음료 주문

큐(queue)란 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조이다.
쉽게 얘기해서 카폐에서 음료를 주문하는 사람들이 줄을 서 있는 모습을 생각하면 된다.
먼저 들어간 사람이 먼저 나온다 fist In fisrt Out!

queue의 method
enqueue(element) - 요소를 큐의 뒤에 추가합니다.
dequeue() - 요소를 큐의 앞에서 제거하고 반환합니다.
size() - 큐의 현재 요소 개수를 반환합니다.


queue 역시 위에 메소드로 이루어진 코드를 작성해보았다.

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

  size() {
    return Object.keys(this.storage).length
  }

  enqueue(element) {
    this.storage[this.rear] = element
    this.rear = this.rear + 1
  }

  dequeue() {
    let result = this.storage[this.front]
    delete this.storage[this.front]
    this.front++
    return result 
  }
}

stack과 queue의 개념은 비교적 간단하게 수훨하게 마무리하였다.
다음에는 linked list와 hash table에 대해 리뷰를 남기겠다.

profile
훌륭한 코드는 훌륭한 문서보다 낫다.

0개의 댓글