Stack & Queue

devPomme·2021년 1월 19일
0

자료구조

데이터의 표현 및 저장 방법

Stack

후입선출(Last in, First out)
예시) 하노이의 탑

필요한 기능

class Stack{
  constructor(){
    this.storage = {}; // 빈 객체
    this.top = -1 // 최상단 요소의 인덱스(빈 배열일 경우 -1)
  }

1) 추가(push(element))

  • 새로운 요소가 추가되었으므로 this.top은 1 증가하고, 업데이트된 this.top을 numeric key로 이용하여 값을 객체에 담는다.
push(element){
  this.top++; // ex) 빈 배열에 새 요소가 추가될 경우 top의 인덱스는 0이 된다.
  this.storage[this.top] = element;
}

2) 삭제(pop())

  • 빈 배열일 경우에는 빈 배열을 그대로 리턴한다.
  • 최상단의 요소를 제거하고 반환한다.
pop() {
  let temp; // 반환할 최상단 요소의 값
  if (this.top === -1) {
    reutnr {};
  } else {
    temp = this.storage[this.top];
    delete this.storage[this.top];
    this.top--;
    return temp;
  }
}

3) 크기 확인(size())

Stack의 크기(엘리먼트의 개수) 확인한다.

size() {
  return this.top+1;
  }

Queue

선입선출(First in, First out)
예시: 영화관 매표소 줄

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; //가장 첫번째 요소의 인덱스값
    this.rear = 0; // 가장 마지막 욧
  }

1) 추가(enque(element))

  • 줄의 가장 끝에 새로운 요소를 추가한다.
enqueue(element){
  this.storage[this.rear] = element;
  this.rear++; // 새로 추가될 요소의 인덱스값
}

2) 삭제

  • 가장 앞의 요소를 storage에서 삭제하고 반환한다.
  • 빈 객체일 경우, 빈 객체를 그대로 리턴한다.
  • 맨 앞의 요소를 제거한 후에는, 바로 뒤의 요소
dequeue(element){
  let temp;
  if (this.size() === 0) {
    return {};
  } else {
    temp = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return temp;
  }
} 

3) 엘리먼트의 개수 확인하기

size() {
  return this.rear - this.front;
}
profile
헌신하고 확장하는 삶

0개의 댓글