📁

Stack / Queue

Stack

데이터를 쌓아올리는 선형 자료구조

한번 마음속으로 상자를 쌓아올려보자. 쌓아올린 상자 중 하나를 꺼내야할 때 우리가 가장 먼저 꺼낼 수 있는 상자는 무엇일까?

어떤 상자를 꺼내더라도 우리는 가장 위에 있는 상자부터 꺼내야한다.

stack도 상자를 쌓는 과정과 같다. 데이터를 쌓아올리는 자료구조이므로 stack에 데이터를 쌓으면 우리가 가장 먼저 꺼낼 수 있는 데이터는 가장 마지막에 쌓아올린 데이터, 즉 가장 마지막에 집어 넣은 데이터이다.

Stack의 큰 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.

이런 스택의 구조를 LIFO (Last In first Out; 후입선출) 라고 부른다.

예시

우리가 자주 사용하는 브라우저에도 Stack을 사용하고있다. 바로 브라우저의 뒤로 가기, 앞으로 가기 기능이다.

prev stack에는 이전에 방문한 페이지를 stack을 통해 저장한다.

뒤로가기를 누르면 prev stack에서 가장 최근에 저장된 페이지를 꺼내오고 next stack에는 현재 페이지를 저장한다.

앞으로 가기를 누르면 prev stack에서 가장 최근에 저장된 페이지를 꺼내오고 현재 페이지를 prev stack에 저장한다.

스택은 정해진 방향으로만 데이터를 쌓을 수 있다.

top은 가장 위에 있는 데이터를 가리키고 있는데 top을 통해서만 데이터에 접근할 수 있으며 데이터를 추가할 때도 top이 가리키는 데이터의 위에 추가된다.

Stack의 연산

push : 요소를 컬렉션에 추가한다.

pop : 아직 제거되지 않은 가장 최근에 삽입된 요소를 추출한다.

JavaScript로 구현하기

class Stack {
    constructor() {
      this.storage = {};
      this.length = 0;
    }
    push(element) {
      this.storage[this.length++] = element;
    }

    pop() {
      if (this.length > 0) {
        let removed = this.storage[--this.length];
        return removed;
      }
    }

    size() {
      return this.length;
    }

    empty() {
      return (this.length ? 0 : 1);
    }

    top() {
      return (this.length === 0 ? -1 : this.storage[this.length]);
    }
}
JavaScript
복사

Queue

데이터를 집어넣을 수 있는 선형 자료구조

우리가 맛집에 들어가기위해 줄을 서있다고 생각해보자. 식당에 가장 먼저 들어갈 수 있는 사람은? 바로 가장 먼저 줄에 선 사람일 것이다.

Queue는 줄과 같다. Stack과는 반대되는 개념으로, 데이터를 집어넣으면 가장 먼저 넣은 데이터가 가장 먼저 나오게된다.

이런 큐의 구조를 FIFO (First In First Out; 선입선출) 라고 부른다.

예시

Queue는 데이터가 입력된 순서대로 처리할 때 주로 사용

컴퓨터 장치들 사이에서 데이터를 주고받을 때에는 각 장치 사이에 존재하는 속도, 시간 차이를 극복하기 위해 임시 기억 장치 buffer를 Queue를 사용해 구현

유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우, 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생

queue는 한 쪽에서는 삽입, 다른 한 쪽에서는 삭제 작업이 이루어진다.

front는 삭제 연산이 수행되는 쪽을 가리키고, rear는 삽입 연산이 수행되는 쪽을 가리킨다.

queue의 연산

enqueue : 요소를 추가

dequeue : 아직 제거되지 않은 가장 먼저 삽입된 요소를 추출한다.

JavaScript로 구현하기

class Queue {
    constructor() {
      this.storage = [];
      this.length = 0;
    }
    push(element) {
      this.storage[this.length++] = element;
    }

    pop() {
      if (this.length !== 0) {
        let removed = this.storage[0];
        this.storage = this.storage.slice(1);
        this.length--;
        return removed;
      }

    }

    size() {
      return this.length;
    }

    empty() {
      return (this.length ? 0 : 1);
    }

    front() {
      return (this.length ? this.storage[0] : -1);
    }

    rear() {
      return (this.length ? this.storage[this.length - 1] : -1);
    }
}
JavaScript
복사