TIL : Stack & Queue

1. 자료구조 (Data Structure)

· 자료 (Data) : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 것

· 자료구조 (Data Structure) : 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것

 

 

자료구조

 

---

2. Stack

· '쌓다', '쌓이다', '포개지다'

· 자료를 쌓는 자료구조

· LIFO(Last In First Out) / FILO(First In Last Out) : 입출이 하나인 제한적 접근

· 활용 => 브라우저에서 뒤로 가기, 앞으로 가기 기능을 구현할 때!

 

---

3. Queue  쿠에우에...?ㅎ-ㅎ

· '줄을 서서 기다리다', '대기 행렬'

· Stack과 반대 개념

· FIFO(First In First Out) / LILO(Last In Last Out) : 먼저 들어간 자료가 먼저 나온다. 선입선출!!

· 활용 => 프린터 (컴퓨터 - Queue(임시 기억 장치)에 하나씩 들어옴 - 들어온 순서부터 인쇄)

· 버퍼 (buffer) : 데이터를 A에서 B로 전송하는 동안 일시적으로 보관하는 메모리 영역

· 버퍼링 (buffering) : 버퍼를 활용하는 방식 => 중앙처리장치와 입출력장치의 속도 차이 해결

· 스풀링 (spooling) : 버퍼링과 비슷한 개념, 순차적 처리 (저장공간 : 버퍼-메모리 일부, 스풀-디스크 일부)

---

4. Stack & Queue 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  size() {
    return this.top; 
  } //this.top은 스택이 쌓일 때마다 하나씩 증가 => 새롭게 추가될 요소의 인덱스
  
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  } //새로 추가될 요소의 인덱스를 나타내는 this.top을 키, 요소를 값으로 하여 storage에 할당
  
  pop() {
    if (this.size() <= 0) {
      return;
    } else {
    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
    } //top-1로 최상단을 설정한 후 변수에 저장하고, 스택에서 삭제
  }
}

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; //가장 앞에 있는 요소
    this.rear = 0; //가장 뒤에 있는 요소
  }
  
  size() {
    return this.rear - this.front;
  } //추가될 때 rear값이 커지고, 삭제될 때 front가 변경되므로!

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  } //새로 추가될 요소의 인덱스를 나타내는 this.rear를 키, 요소를 값으로 하여 storage에 할당

  dequeue() {
    if (this.size() === 0) {
      return;
    } else {
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
    } //this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제
  }
}