스택 / 큐

Stack

데이터를 순서대로 쌓는 자료구조

후입 선출(LIFO: Last In First Out)의 구조를 가지고 있다. (1, 2, 3) ⇒ (1, 2, 3, 4) - 4 입력 (1, 2, 3, 4) ⇒ (1, 2, 3) - 4 출력

입출력이 하나만 존재한다. 스택의 최상단 위치에서만 값을 넣거나 빼게 된다.

데이터는 하나씩 넣고 뺄 수 있다. 한번에 여러개의 데이터를 뺄 수 없고, 마찬가지로 한번에 여러개를 넣을 수 없다. 많은 데이터를 다루기 위해서는 반복문으로 하나씩 입출력을 해야 한다.

스택에 데이터가 다 찬 상태에서 새로운 데이터를 삽입하게 되면 “스택 버퍼 오버플로” 에러가 발생한다.

Stack의 실사용 예제

대표적으로 “브라우저의 뒤로 가기, 앞으로 가기” 와 “JavaScript의 실행 컨텍스트” 가 있다.

새로운 페이지로 이동할 때 현재 페이지를 Prev Stack에 저장

뒤로 가기 버튼으로 페이지를 이동하면 현재 페이지를 Next Stack에 저장하고 Prev Stack에 있는 가장 최상단의 페이지를 현재 페이지로 꺼내옴

앞으로 가기 버튼으로 페이지를 이동하면 현재 페이지를 Prev Stack에 저장하고 Next Stack에 있는 가장 최상단의 페이지를 현재 페이지로 꺼내옴

JavaScript Stack 코드


class Stack {
	constructor {
		this.storage = {};
		this.top = -1;
	}
	
	size() {
		return this.top + 1;
	}

	push(element) {
		this.top += 1;
		this.storage[this.top] = element;
	}

	pop() {
		if(this.size() <= 0)
			return;

		const result = this.storage[this.top];
		delete this.storage[this.top];
		this.top -= 1;

		return result;
	}
}

스택에서 가장 먼저 출력되는 위치를 top이라고 부르며 새로운 데이터가 스택에 입력될 때 마다 top의 크기가 1씩 커진다.

현재 top의 데이터를 출력하면, 크기가 1씩 작아진다.

새로운 데이터를 입력하는 메서드를 Push / 출력하는 메서드를 Pop으로 부른다.

Queue

데이터를 줄을 세워서 저장하는 자료구조

선입 선출(FIFO: First In First Out)의 구조를 가지고 있다. (1, 2, 3) ⇒ (1, 2, 3, 4) - 4 추가 (1, 2, 3, 4) ⇒ (2, 3, 4) - 1 제거

두 개의 입출력 방향을 가지고 있다. Queue는 front와 rear로 구성되어 데이터를 출력할 때는 front로 출력을 하고, 새로운 값을 넣을 때는 rear로 입력을 하게 된다.

데이터는 하나씩 넣고 뺄 수 있다. Stack과 마찬가지로 데이터는 하나씩만 입,출력이 진행된다.

Queue는 새로운 값을 입력받을 때 항상 rear를 통해 마지막 위치에 꼬리처럼 저장한다. 그리고 값을 출력할 때 가장 앞 위치부터 마지막까지 출력한다. 이로 인해, Queue에서 출력된 데이터의 공간은 접근할 수 없다.

Queue의 실사용 예제

대표적으로 “컴퓨터의 프린트” 가 있다.

컴퓨터에서 어떤 문서를 인쇄 요청을 하면, 설정에 따라 문서의 순서를 Queue에 순서대로 입력한다.

Queue에 모든 문서가 들어갔다면, 먼저 들어온 순서부터 인쇄를 시작한다.

또한, 프린터나 동영상 시청 등 컴퓨터 장치끼리 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나, 시간 차이를 극복하기 위해 “buffer”를 사용한다.

이 buffer가 Queue로 만들어져 있다.

동영상 시청의 경우, 영상을 실행할만한 데이터가 buffer에 담기기 전까지 진행이 되지 않고 대기 상태가 되는데, 이것을 “buffering” 이라고 한다.

JavaScript Stack 코드


class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front
  }
	
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
  dequeue() {
    if(this.size() <= 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

새로운 데이터를 입력하는 메서드를 Enqueue / 출력하는 메서드를 Dequeue 로 부른다.

Circle Queue(원형 큐)

마지막 위치와 시작 위치가 연결되는 원형 구조를 띈 Queue

기존 Queue의 단점인 출력된 위치 공간을 사용할 수 없다는 점을 해결할 수 있다.

Queue의 마지막 저장 공간 위치까지 rear가 계속 커지다가 처음 공간 위치로 수정된다.

데이터가 모두 차기 전 까지 반복적으로 이어진다.

Priority Queue(우선순위 큐)

데이터의 우선순위에 따라 출력하는 Queue