js_자료구조 / Stack , Queues

알고리즘 자료구조 정말 난해하고 어려운 개념입니다. 개념은 그렇게 어렵지는 않지만 응용하기가 너무 힘든 내용이라고 생각합니다. 이번 블로깅은 자료구조의 기본 개념인 Stack과 Queues에 대해 블로깅을 해보도록 하겠습니다.

---

# 스택(STACK) 이해하기

스택이란 쌓아 올린다는 것을 의미합니다. 쉽게 비유하자면 스택 자료 구조라는 것을 탄알집에 총알을 넣어 차곡차곡 쌓아 올린 형태의 자료 구조를 말합니다.

 

이미지로 이해하는 스택 원리

push를 하면 순서대로 쌓인다.

 

pop()을 하면 위에서 부터 빠져 나온다.

 

스택의 특징

스택은 위의 예시 사진 처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있습니다. 

맨 위에서만 접근 할 수 있으며 가장 최근에 들어온 자료를 가리킵니다. 

삽입 연산은 'push', 삭제는 'pop'연산자를 씁니다.

 

따라서 스택은 시간 순서에 따라 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 특징을 가지고 있으며 이러한 구조를 LIIFO(Last-In-First_Out)구조라고 합니다.

 

 

스택은 어디서 활용 될까요 ?

스택은 LIFO구조 즉 후입선출을 활용한 분야에서 사용 합니다.

웹 브라우저 뒤로가기, 앞으로가기 구현 실행 취소(undo), 역순 문자열 만들기 등 

 

Stack 코드 구현

 

class Stack {
  constructor() {
      //data 저장 공간
    this.storage = {};
    //저장공간의 key
    this.top = 0;
  }
    //data의 사이즈(길이)를 표현
  size() {return Object.keys(this.storage).length}
  
  //(중요)push 는 push 했을때 저장공간을 나타내야 한다
  push(element) {
 
    //obj 형식이니 obj 형식대로 추가
    //key는 top의 값으로 value는 element로 넣어준다.
    this.storage[this.top] = element
      //push가 됬으므로 저장공간의 data 위치 +1
    this.top++
 
  }
    //(중요)pop은 pop 했을때 제거된 항목을 저장하므로 저장공간을 나타내는게 아니다.
  pop() {
      //변수선언 result data 저장공간[최근 data 위치]
    let result = this.storage[this.top-1]
    //없애준다 최근 data를
    delete this.storage[this.top-1]
    //data 저장공간에서 없어졌으니 top도 변화가 필요 -1
    this.top--
    //없애준 data 반환해야하니 return result
    return result
  }
}

 

---

# 큐(QUEUE) 이해하기

큐는 앞서 배운 Stack과 같이 요소를 추가,제거를 할수 있지만 방식이 다릅니다. 큐는 줄, 혹은 줄을 서서 기다리는 것을 의미하며 이것은 선입선출 FIFO(First In First Out)방식 자료구조라고 부릅니다.

 

 

이미지로 이해하는 스택 원리

앞에서 빠져 나오넹 ?ㅎㅎ

 

큐의 특징

큐는 한쪽 끝에서 삽입, 다른쪽 끝에서 삭제 작업이 양쪽에서 이뤄 집니다. 

이떄 삭제연산만 가능한 곳이 프론트(front), 삽입 연산만 이루어 지는 곳을 리어(rear)로 정하고 각각 연산작업을 하면 됩니다. 이때 큐의 리어에서 이뤄지는 삽입 연산을 인큐(enQueue), 프론트에서 이뤄지는 삭제 연산을 디큐(dnQueue) 라고 부릅니다.

 

 

큐는 어디서 활용 될까요 ?

큐는 FIFO구조 즉 선입선출을 활용한 분야에서 사용 합니다.

프린터의 인쇄 대기열, 은행 업무, 콜센터 대기시간, 프로세스 관리 등등

 

 

Queue 코드 구현

 

class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈를 구합니다.
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 
  //각 값을 알아야 size를 구할 수 있습니다.
  size() {
    return Object.keys(this.storage).length
    //return this.rear - this.front;
  }
  // queue에 element를 추가합니다.
  // 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. 
  //this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}