이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌12 - Algorithm - 2년 전 등록

자료구조(큐, queue)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 에 대해 알아보겠습니다.

는 실생활에서 줄이라고 생각하시면 됩니다. 우리가 순서를 기다릴 때 줄을 서죠? 새로 온 사람은 줄 맨 뒤에 서고, 제일 앞 사람은 필요한 행동을 한 후 빠집니다. 이렇게 뒤에서 들어가고(enqueue) 앞에서 빠지는(dequeue) 구조입니다. 자바스크립트의 배열로 따지면 push(enqueue)와 shift(dequeue) 메소드만 있는 거라고 생각하시면 됩니다. 거기에 추가로 제일 앞의 데이터를 알 수 있는 front가 있습니다.

이제 코드로 큐를 만들어볼까요?

var Queue = (function() {
  function Queue() {
    this.count = 0;
    this.head = null;
    this.rear = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Queue.prototype.enqueue = function(data) {
    var node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
  };
  Queue.prototype.dequeue = function() {
    if (!this.head) { // stack underflow 방지
      return false;
    }
    var data = this.head.data;
    this.head = this.head.next;
    // this.head 메모리 클린
    --this.count;
    return data;
  };
  Queue.prototype.front = function() {
    return this.head && this.head.data;
  };
  return Queue;
})();
var queue = new Queue();
queue.enqueue(1); // 1
queue.enqueue(3); // 2
queue.enqueue(5); // 3
queue.dequeue(); // 1
queue.front(); // 3

스택에는 제일 위를 가리키는 top만 있었다면 에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear 두 개가 있습니다.

특수한 도 있습니다. 순환 큐가 그 중 하나인데요. frontrear가 연결되어 있습니다. 예를 들면 1, 2, 3의 데이터가 들어있는 큐가 있을 때 원래라면 3에서 끝나지만, 순환 큐는 rear인 3에서 다시 front인 1로 넘어갑니다. 코딩은 그냥 this.rear.next = this.front를 추가해주면 구현할 수 있습니다. 순환 큐가 사용되는 이유는 메모리 관리가 쉽기 때문인데 자바스크립트에서는 메모리를 알아서 정리해주기 때문에 그 효용성이 조금 떨어집니다. 

또 다른 큐로는 우선순위 큐가 있습니다. enqueue, dequeue는 같지만, enqueue할 때 제일 뒤에 넣는 게 아니라 우선순위 순서를 따져서 데이터를 넣습니다. 어떤 데이터가 우선순위가 높은지는 프로그래머가 직접 정해주면 됩니다. 문제는 우선순위 큐는 위와 같이 큐로 구현하면 데이터를 삽입하기 힘들다는 단점이 있습니다. 그래서 주로 이라는 자료구조를 사용해서 구하는데요. 힙을 알기 위해서는 또 트리를 알아야합니다.

다음 시간에는 트리(tree)에 대해 알아보겠습니다!

목록
투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

아직 댓글이 없습니다.