자바스크립트_자료구조 stack과 queue 개념 정리

오늘은 자료구조에서 stack과 queue에 대해서 알아보겠습니다.

 

먼저 자료구조가 무엇인지 설명해보겠습니다.

자료구조란 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 것들을 우리는 자료라고 합니다. 자료들이 잘 분석되고, 정리되고 활용되어야만 의미가 있다고 볼 수 있는데, 무분별하게 마구잡이로 자료를 체계없이 저장하면 의미가 없어집니다.

 

자료를 구조화 시키는 것.

그렇기에 우리는 잘 정리된 자료를 활용하기 위해 자료 구조를 갖추려고 하는 것입니다.

 

Stack

stack이란 후입선출(LIFO, Last-in-first-out)의 구조이다.

스택은 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

만약 0-1-2-3-4-5 순으로 쌓았다면, 5-4-3-2-1-0 순으로 빼낼 수 있다.

스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 특징을 가진다.

쌓여있는 접시를 생각하면 이해가 쉽다.

 

 

 

스택에서 데이터를 삽입하는 연산을 'push'

삭세하는 연산을  'pop'이라고 한다.

 

queue

Queue는 FIFO(first-in-first-out)의 구조를 가진다.

먼저 넣은 데이터가 먼저 나오는 구조

 

톨게이트를 생각하면 이해가 쉽다. 톨게이트는 자료구조이고, 자동차를 데이터로 비유하면, 가장 먼저 진입한 자동차가 가장 먼저 톨케이트를 통과한다. 

queue는 입력된 순서대로 처리할 때 주로 사용된다.

 

큐 자료구조는 각 장치 사이에 존재하는 속도의 차이나 시간의 차이를 극복하기 위해 사용된다.

이것을 통틀어 버퍼(buffer)라고 한다. 

 

 

•   stack구현

stack이란 class를 만들고, 그안에 .constructor를 만들어준다.

push메소드를 사용할때 el라는 인자를 받으면 그 인자를 storage안에 넣어주고, top의 길이는 1이 된다.

pop의 경우는 사이즈가 0보다 크다면 가장 최근에 들어온 데이터 하나를 지우고, top도 하나 지운다. 

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
 
  size() {
    return this.top;
  }
 
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
 
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
  }
}

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    return this.rear - this.front;
  }
  
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}