[2020. 10. 20 TIL] Data Structure - Stack, Queue

Young-mason·2020년 10월 22일
0

TIL

목록 보기
3/11

Stack의 정의

A LIFO data structure!

The last element added to the stack will be the first element removed from the stack

Property

  • top : stack 가장 위에 쌓여있는 데이터의 위치값(index).
  • maxSize : maxSize는 해당 저장소의 최대 크기를 나타냄
  • stackArray : 저장소 그 자체

Method

  • push(): 배열 가장 뒤 값을 추가시키는 메소드
  • pop() : 배열의 가장 뒤의 값을 삭제하는 메소드. 꺼낸 값은 출력하거나 다른 곳에 할당할 수 있음.
  • empty() : 저장소가 비어있는지 여부에 따라 boolean 값 리턴
  • size() : 현재 저장소에 저장되어있는 데이터의 개수 반환

Javascript 를 이용하여 Stack 을 구현해보기

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

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top++;
  }

  pop() {
    let topVal = this.storage[this.top-1];
    delete this.storage[this.top-1];

    if(this.top > 0){
      this.top--;
    }

    return topVal;
  }
}

Queue의 정의

A FIFO data structure
First In First Out
선입선출


How do we use them in programming?

  • Background tasks
  • Uploading resources
  • Printing / Task processing

Queue는 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. (위키백과)

Javascript 를 이용하여 Queue 을 구현해보기

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

  size() {
    return this.rear;
  }

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

  dequeue() {
    let frontVal = this.storage[this.front];
    delete this.storage[this.front];

    for(let i=1 ; i<this.rear ; i++){
      let curr = this.storage[i];
      this.storage[i-1] = curr;
    }

    if(this.rear > 0){
      this.rear--;
    }
    delete this.storage[this.rear];
    return frontVal;
  }
}
profile
Frontend Developer

0개의 댓글