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

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;
  }
}