자료구조 1. Stack, Queue

1. Stack

Stack

  Stack은 목록의 끝(top/스택포인터)에서만 데이터를 입력(push)과 출력(pop)할 수 있는 자료구조이다. 따라서 나중에 입력된 데이터를 먼저 꺼내며 이를 LIFO(Last In First Out/후입선출) 구조라고 한다. 

 

  한편 Stack의 데이터를 담을 수 있는 최대치(limit)가 존재한다. Stack이 담은 데이터량이 한계치에 도달하였을 때(스택이 꽉 찬 상태) 입력(push)을 수행하면 해당 데이터를 입력할 수 없으므로 Overflow가 발생한다. 반대로 Stack에 데이터가 없는 경우 출력(pop)을 수행하면 출력할 데이터가 존재하지 않으므로 Underflow가 발생한다. Overflow와 Underflow라는 상황을 방지하기 위해 Stack에 입출력을 하기 전 full 검사, empty 검사를 수행하는 것이 좋다.

 

Stack의 입출력은 다음과 같은 그림으로 나타낼 수 있다.

 

Stack 데이터 입력(Push)

stack 데이터 출력(pop)

  Stack을 JavaScript Object로 구현하면 다음과 같다.(Stack의 한계는 무한이라 가정)

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

  size() {
    return Object.keys(this.storage).length;
  }

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

  pop() {
    if (this.size() > 0) {
      let value = this.storage[this.top];
      delete this.storage[this.top];
      this.top--;
      return value;
    }
  }
}

 

 

2. Queue

queue

  Queue은 목록의 한쪽 끝에서는 데이터를 입력(enqueue)만, 다른 한쪽 끝에서는 출력(dequeue)만할 수 있는 자료구조이다. Queue는 데이터가 입력된 순서대로 출력된다. 즉, 가장 먼저 입력된 자료가 가장 먼저 출력되는 FIFO(First In First Out, 선입선출) 구조이다. Queue에서 데이터의 출력이 이루어지는 곳은 front, 데이터의 입력이 이루어지는 곳을 rear라 한다.

 

  한편 Queue도 데이터를 담을 수 있는 최대치(limit) 가 존재한다. Queue가 꽉 찬 상태에서 데이터를 입력(enqueue)하면 Overflow, Queue가 빈 상태에서 데이터를 출력(dequeue)하면 Underflow가 발생한다. Overflow와 Underflow라는 상황을 방지하기 위해 Queue에 입출력을 하기 전 full검사, empty 검사를 수행하는 것이 좋다.

 

  Queue를 JavaScript Object로 구현하면 다음과 같다.(Queue의 한계는 무한이라 가정)

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; //가장 오래된 요소의 위치
    this.rear = 0; //다음에 추가될 요소의 위치
  }

  size() {
    return Object.keys(this.storage).length;
  }

  enqueue(element) {
    this.storage[String(this.rear)] = element;
    this.rear++;
  }

  dequeue() {
    if (this.size() > 0) {
      let value = this.storage[this.front];
      delete this.storage[this.front];
      this.front++;
      return value;
    }
  }
}

 

2-1. Circular Queue(환형큐/원형큐)

Circular Queue

  배열(선형)의 형태로 Queue를 구현하면 새로운 원소가 계속 들어올 때 Queue의 길이가 계속 증가한다는 문제점이 있다. 예를들어 선형 Queue에서 5번 데이터를 입력(enqueue) 하고 1번 데이터를 출력(dequeue)해보자. 이 경우 Queue 앞쪽에서 데이터를 출력(dequeue)하며 빈 공간이 하나 생기는데 이 빈 공간은 다시는 사용할 수 없게 된다. 이 공간을 다시 재사용할 수 있도록 Queue의 상한과 하한을 연결하여 원형으로 순환구조를 갖추게 만든 자료구조가 Circular Queue이다.

 

2-2. Priority Queue(우선순위 큐)

  일반적인 Queue와 달리 데이터를 출력할 때 입력 순서와 상관없이 우선순위가 높은 데이터를 먼저 출력하는 Queue가 Priority Queue이다. Priority Queue는 데이터 입력, 출력 시 데이터의 우선순위에 따라 Queue에 존재하는 데이터들이 한 칸씩 밀리거나 당겨지는 일이 발생할 수 있다. 따라서 Heap 자료구조를 사용하여 구현한다. Priority Queue는 운영체제의 작업스케줄러(SJF/최단작업우선스케줄링 등)에 사용된다.

  자세한 설명은 Priority Queue 포스팅에서 알아보자.

3. Stack과 Queue

  Stack은 후입선출, Queue는 선입선출의 구조를 갖는 자료구조이다. 따라서 Stack과 Queue의 가장 큰 차이점은 데이터 출력(삭제)동작이다. Stack은 나중에 저장된 데이터가 먼저 출력되고, Queue는 먼저 저장된 데이터가 먼저 출력되기 때문이다. 

  Stack은 브라우저의 뒤로가기 버튼처럼 후입선출이 필요한 경우에 사용된다. 그 외에도 함수 호출, 실행 취소, DFS에 사용된다.  Queue는 가게의 대기열처럼 순서대로 작업이 처리되어야하는 경우에 사용된다. 그 외에도 운영체제의 메시지 처리(메시지 큐), 캐시 구현, BFS 등에 사용된다.