코드 보관함: [자료 구조] 큐(Queue)

자바(Java)로 구현한 큐(Queue) 예제

큐(Queue) 컨셉

큐(Queue)란 무었인가?

큐는 직선형 자료 구조로써, 같은 타입의 데이터를 "하나 다음 하나" 라는 컨셉으로 순차적으로 저장하는 자료형이다. 스택(Stack)과는 달리, 큐(Queue)는 구조의 양 끝 모두에 접근이 가능하다. 맥도날드나 카페에서 줄을 서서 기다리는 걸 머리속에 그려보자. 줄은 새로운 사람이 끝에 섬으로써 길어지고, 가장 앞에선 사람이 주문을 함으로써 짧아진다. 이게 바로 큐(Queue)이다. 이렇한 이유로, 큐(Queue)는 보통 "FIFO(First In First Out) Structure"(먼져 들어간게 먼져 나오는 구조)라 영어권에서 표현된다.

큐(Queue) 실제로 어디에 쓰일까?

Operating System

시스템 스케줄링, 인풋 버퍼(Input Buffer), 그리고 프린터 작업 관리 등

큐(Queue)는 어떻게 구현될까?

큐(Queue)는 스택(Stack)처럼 추상 자료형(Abstract Data Type)이므로, 다양한 방법으로 구현될 수 있다. 자바(Java)로 구현할 때 가장 많이 쓰이는 두가지 방법은 배열(Array)와 링크드 리스트(Linked List)를 이용하는 것이다. 큐(Queue)는 몇가지 필수적인 메소드들을 가지고 있는데 그것들은 아래와 같다

Enqueue(삽입)

큐(Queue)의 끝에 새로운 자료를 삽입한다
이 작업은 O(1)의 복잡도를 가진다

Dequeue(제거)

큐(Queue)의 가장 첫 위치에 존재하는 자료를 반환하고 제거한다.
이 작업은 O(1)의 복잡도를 가진다

Peek

큐(Queue)의 처음에 존재하는 자료를 반환한다
Dequeue 메소드와는 달리, 처음에 존재하는 자료를 제거하지는 않는다.

isEmpty

큐(Queue) 가 Empty 상태인지 확인한다.

clear

큐(Queue) 내부의 모든 자료들을 삭제한다

아래는 자바(Java) 배열(Array)로 구현한 큐(Queue)의 예제이다

public class QueueWithArray {
 private Object[] queue;
 int first, last, size;
  public QueueWithArray(int size) {
  queue = new Object[size];// 주어진 인터져 size 값으로 size의 크기를 가진 오브젝트 어레이를 생성한다.
  first = last = -1;
  // 우선 아무것도 없는 배열에서, 우리의 마지막, 첫번째 데이터를 가리키는 first, last 인스턴스는 -1인덱스를 가리킨다.       
  this.size = size;// clear 메소드를 위해 사이즈 값을 저장해두자.
 }

 public boolean isEmpty() {
  return first == -1;
  // 만약 first 포인터 인스턴스가 -1 의 인덱스를 가리킨다면 그건 큐(Queue)가 empty 상태라는 뜻이다
 }

 public void clear() {
  queue = new Object[size]; // 새로운 배열(Array)를 생성하면서 원래 큐를 지워버리자
  first = last = -1;// 포인터 인스턴스를 리셋해준다.
 }

 public boolean isFull() {
   // 큐(Queue)가 꽉 찾는지를 확인한다.
   if ((first == 0 && last == size - 1) || first == last + 1) {
   // first 포인터가 인덱스 0, last 포인터가 배열의 마지막 인덱스(size - 1)를 가리키거나
   // first 포인터가 가리키는 인덱스가 last 포인터가 가리키는 인덱스보다 1이 크다면
   // 이는 큐(Queue)에 쓰는 배열이 꽉 찾음을 의미한다.
   return true;
  } else {
   return false;
  }

 }

 public void enQueue(Object e) {
  if (isFull()) {
   throw new FullQueueException();// 큐가 꽉 찾다면 Exception을 던져주자
  } else {
   //아니라면 삽입을 시작한다.
   if (first == -1) {// 만약 first 인스턴스가 -1값을 가지고 있다면, 이는 큐가 empty 상태인걸 의미한다.
    first = last = 0;// 그렇니 first 와 last 값을 0으로 바꿔주자
   } else {
    last = (last + 1) % size;
    // 이 메소드에서 새로운 object e 는 어레이의 가장 끝 인덱스의 위치로 삽입된다.
    // (last + 1) % size 는 배열(Array)의 중간에 last 인덱스가 위치할 경우를 생각한다.
   }
   queue[last] = e;
  }
 }

 public Object dequeue() {
  if (isEmpty()) {
   // 큐(Queue)가 Empty 인지 확인한다
   throw new EmptyQueueException();
  } else {
   Object toReturn = queue[first];
   if (first == last) {
    // first 와 last 가 같은 인덱스를 가리킨다면
    // 이는 큐(Queue)에 데이터가 1개밖에 없음을 의미한다.
    // 그렇니 그냥 포인터를 리셋해주자
    first = last = -1;
   } else {
    first = (first + 1) % size;
    // 만약 first 포인터가 배열(Array)의 마지막 인덱스를 가리키고 있다면
     // first + 1 은 ArrayOutOfBound Exception 을 낳을 것이다
     // first = (first + 1) % size; 은 그럴경우에는 0 이란 수가 계산되어
     // 옭바른 인덱스를 계산 할 수 있다.
   }
   return toReturn;
  }
 }

 public Object peek() {
  if (isEmpty()) {
   throw new EmptyQueueException();
  } else {
   return queue[first];
  }
 }
}

아래는 자바(Java) Linked List 로 구현한 큐(Queue)의 예제이다

import java.util.LinkedList;
public class QueueWithLinkedList {
 private LinkedList queue;

 public QueueWithLinkedList() {
  queue = new LinkedList();
 }

 public boolean isEmpty() {
  return queue.isEmpty();
 }

 public void enQueue(Object e) {
  queue.addLast(e);
 }

 public Object deQueue() {
  return queue.removeFirst();
 }

 public Object peek() {
  return queue.getFirst();
 }
}

코드 보관함

2015년 1월 7일 수요일

[자료 구조] 큐(Queue)