[Section 4] Stack. Queue

자료구조

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

---

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻
데이터를 순서대로 쌓는 자료구조

LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출

• 통이 수직으로 세워져있는 형태
• 데이터를 넣고 빼는 구멍이 윗쪽 한 곳
• 데이터를 넣을때 -> 윗쪽
• 데이터를 뺄 때 -> 윗쪽
• 윗쪽에 있는(가장 마지막에 넣은) 데이터부터 뺄 수 있는 후입선출 형

페이지 내 이전, 다음 페이지에 활용

 class Stack {
 // stack constructor를 생성
 constructor() {
   this.storage = {};
   this.top = -1;
 }
 // stack의 사이즈
 // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로부터 size를 구할 수 있다.
 // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타낸다다. 빈 스택을 표현하는 -1부터 1씩 증감하며 표현하며 전체 요소의 개수를 추정할 수 있다
 size() {
   return this.top + 1;
 }
 // stack에 element를 추가한다.
 // 현재 추가하는 element의 인덱스인 this.top을 키로, 요소를 값으로 하여 storage에 할당한다.
 push(element) {
   this.top += 1;
   this.storage[this.top] = element;
 }
 // 만약 size가 0보다 작거나 같다면 이는 비어있는 스택을 의미하므로 아무 일도 일어나지 않는다.
 // stack에서 현재 stack의 최상단에 있는 element를 변수에 저장합니다.
 // storage에서 해당 element를 제거한다.
 // 하나를 제거했으니 방금 제거한 element의 인덱스를 나타내는 top 또한 감소시켜 업데이트 해준다.
 // 최상단에 있던 element가 저장된 변수 result를 반환한다.
 pop() {
   if (this.size() <= 0) {
     return;
   }
   const result = this.storage[this.top];
   delete this.storage[this.top];
   this.top -= 1;
   return result;
 }
}

---

Queue

큐(Queue)는 줄을 서서 기다리다, 대기행렬이라는 뜻
스택과 반대되는 개념

• 통이 수평으로 세워져 있는 형태
• 데이터를 넣고 빼는 구멍이 양쪽 두 군데
• 데이터를 넣을때 -> 뒷 쪽
• 데이터를 뺄 때 -> 앞 쪽
• 앞 쪽에 있는 (가장 처음에 넣은) 데이터부터 뺄 수 있는 선입선출(FIFO) 형

  class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있다.
  size() {
    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;
  }
}