스택 & 큐

효율적인 프로그래밍을 하기 위해선 자료구조 개념은 정말 필수적이라고 생각한다.
그 중에 스택 & 큐는 자바스크립에서 흔히 쓰는 개념이다.

대표적으로 Array메서드 push, pop, unshift등등 사용하는 경우가 많은데 이는 스택과 큐에서도 적용할 수 있는 개념이다.

한번 제대로 이해하고 가자.

스택(Stack)

Stack = 쌓아 올리다

스택은 책처럼 데이터를 쌓아올리는 구조이다.

프로그래밍적으로 생각해보면 데이터(자료)의 입출력이 한방향에서만 이루어지는 구조이다.

• Top : 현재 데이터 기준의 최 상단
  ex) 위 그림으로 판단하면 x -> 1 -> 2 ->1
  info) 모든 데이터 연산은 Top에서 이루어진다.

• Push: 데이터가 추가되는 연산이다.
  ex) Top을 기준으로 계속해서 쌓이는 구조 (1 ->2->3-> ...)
  info)JS 내장메서드 Push와 같은 기능이다.

• Pop: 데이터를 제거(삭제)하는 연산이다.
  ex) Top을 기준으로 데이터를 하나씩 제거한다.(3->2->1->x)
  info) JS 내장메서드 Pop과 같은 기능이다.

구현 in Javascript

class Stack {
  constructor(){
    this.storage = {};
    this.top = 0;
  }
  
  size() {
    return this.top
  }
  
  push(element){
    this.top ++;
    return (this.storage[this.top] = element);
  }
  
  pop(){
    if(this.top != 0){
      let data = this.storage[this.top];
      delete this.storage[this.top];
      this.top--;
      return data;
    }
  }
}

var test= new Stack
test.push('가')//storage: { '1': '가'}
test.push('나')//storage: { '1': '가', '2': '나' }
test//storage: { '1': '가', '2': '나' },
test.pop()//storage: { '1': '가'}
test.size()//1

후입선출구조이다.
나중에 push된 '나'가 먼저 pop되는 구조이다.

큐(Queue)

Queue = 줄을 서다.

큐는 데이터 In&Out을 한곳에서 관리하는 스택과는 달리
In&Out각각 수행된다.

• Rear : 데이터가 입력되는 부분
• Front : 데이터가 추출되는 부분
• Enqueue : 데이터 입력 수행을 일컫는 말
• Dequeue : 데이트 추출 수행을 일컫는 말

구현 in Javascript

class Queue {
  constructor(){
    this.storage ={};
    this.front = 0;
    this.rear = 0;
  }
  
  size(){
    return this.front;
  }
  
  enqueue(element){
    if( this.front === 0){
      this.storage[this.front] = element;
      this.front++;
      return
    }
    this.front++;
    let values = Object.values(this.storage)
    values.unshift(element);
    this.storage = {};
    for(let z = values.length -1; z>=0; z--){
      this.storage[z] = values[z]
    }
  }
  
  dequeue() {
    if(this.front !== 0){
      let data = this.storage[this.front - 1];
      delete this.storage[this.front -1];
      this.front --;
      return data;
    }
  }
}

var test2 = new Queue
test2.enqueue('가')//storage: { '0': '가'}
test2
test2.enqueue('나')//storage: { '0': '나', '1': '가' }
test2
test2.dequeue()//storage: { '0': '나'}
test2

먼저 입력되었던 데이터'가'가 삭제 작업시 먼저 사라짐을 알 수 있다.