Stack vs Queue

Stack

팬케이크를 쌓으면 이런 모양이 될 것이다. 가장 먼저 만들어진 것이 아래로 가고 최근에 구운 것이 맨 위로 올라가게 된다. 물론 먹을 때도 맨 위부터 먹게 될 것이다.

이렇게 마치 수직구조처럼 가장 나중에 있는 요소가 먼저 처리되는 것이 Stack이다.

스택은 쌓아올린 자료구조를 의미한다. 스택은 다음과 같은 특징을 가진다.

• 나중에 쌓아올린 자료가 가장 먼저 삭제되는 LIFO(Last In First Out)구조다.
• 크게 push(삽입)와 pop(삭제)으로 이루어져있다.

스택은 다음과 같이 활용된다

1. 이전의 자료를 저장해두고 사용해야 하는 상황

• 웹 페이지의 뒤로가기
  (가장 최근에 보여준 페이지부터 보여준다)
• 재귀함수 호출
  (임시 데이터를 stack에 저장하고 최근 함수부터 reture)
• 실행취소

2. DFS

javascript로 구현하게 되면 다음과 같다.

class Stack{
  constructor(){
    this.arr = [];
    this.top = 0;
  }
  //추가
  push(value){
    this.arr[this.top++] = value;
  }
  //삭제
  pop(){
    //요소가 아무것도 없다면 -1
    if(this.top <= 0) {
      return -1;
    } else {
      //index는 top보다 항상 1이 작다.
      let popped = this.arr[this.top-1];
      //arr는 마지막 요소를 삭제한 새로운 배열로 만든다.
      this.arr = this.arr.slice(0, this.top-1);
      this.top--;
      //삭제된 요소를 리턴
      return popped;
    }
  }
}

const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack) // {arr: [1,2,3], top: 3}
console.log(stack.pop())  // 3
console.log(stack.pop())  // 2
console.log(stack.pop())  // 1
console.log(stack)  // {arr: [], top: 0}

Queue

살다보면 기다려야 하는 하는 순간들이 많다. 나보다 먼저 온 사람이 먼저 은행일을 처리하거나 물건을 사거나 놀이기구를 탈 수 있 수 있었다. 내가 맨 뒤에 있다면? 맨 앞까지 올 때까지 기다려야 한다.

큐는 이와 같이 일방향 터널과 같은 구조이다. 큐는 다음과 같은 특징을 가진다.

• 가장 먼저 들어온 자료가 먼저 나가는 FIFO(First In First Out)구조다.
• dequeue(맨 앞 요소 삭제) 와 enqueue(요소 추가) 작업이 있다.

큐는 크게 두가지로 활용하게 된다.

1. 순서대로 처리해야 할 요소가 있을 경우

• 영상 재생의 버퍼링
  (영상의 뒷부분이 로드될 때 까지 작업을 기다린다)
• 프린트 대기열, 출력
  (프린트의 처리속도가 컴퓨터의 연산속도보다 느리기 때문에 대기시켜서 순차적으로 처리)

2. BFS

BFS와 DFS에 대해서는 다음에 다루도록 할 것이다.

Javascript로 구현하면 다음과 같다.

class Queue{
  constructor(){
    this.queue = {};
    //가장 앞의 요소
    this.head = 0;
    //가장 뒤의 요소
    this.tail = 0;
  }
  //맨 뒤의 요소 추가
 enqueue(element) {
  this.queue[this.tail] = element;
   //가장 뒤의 요소 index 증가
   this.tail++
 }
  //맨 앞의 요소 삭제
 dequeue() {
   //요소가 아무것도 없는 경우
   if (this.tail === this.head){
    return undefined
   }else{
    //맨 앞의 삭제할 값을 미리 정의
    let element = this.queue[this.head];
    //맨 앞의 요소 삭제
    delete this.queue[this.head];
    //head index는 앞으로 증가
    this.head++
    //삭제한 값 리턴
    return element;
   }
  }
}