[자료구조] Java 원형 큐(Circular Queue), 우선순위 큐(Priority Queue), 데크(Deque-double ended queue)

Java 원형 큐(Circular Queue), 우선순위 큐(Priority Queue), 

데크(Deque-double ended queue)

1. 원형 큐(Circular Queue)

배열을 이용한 큐는 이미 사용한 영역인 front의 앞부분에 대해서 다시 활용을 못하기 때문에 메모리를 낭비한다는 단점이 있었다.

그리고 이동 큐를 이용하여 큐가 다 찼을 경우 데이터들을 앞쪽으로 이동시켜 사용하는 방법이 있지만 남아있는 모든 데이터를 다 이동시켜야 한다는 불편한 작업을 수행해야 하기 때문에 그리 효율적으로 동작하지 못한다고 했었다.

[JAVA/알고리즘,자료구조] - [자료구조] Java 큐(Queue) 정리 (배열, 연결리스트)

원형 큐는 이와같은 단점을 보완하는 구조로 큐의 맨 끝과 맨 처음이 연결된 형태의 구조이기 때문에 이미 꺼내어 사용한 큐의 앞부분에 다시 데이터를 저장하여 재사용이 가능한 형태의 큐이다.

public class CircularQueue {          // 큐 배열은 front와 rear 그리고 maxSize를 가진다.         private int front;         private int rear;         private int maxSize;         private Object[] queueArray;                  // 큐 배열 생성         public CircularQueue(int maxSize){                          this.front = 0;             this.rear = -1;                          // 실제 크기보다 하나 크게 지정한다 (공백과 포화를 막기 위함)             this.maxSize = maxSize+1;                 this.queueArray = new Object[this.maxSize];         }                  // 큐가 비어있는지 확인         public boolean empty(){             return (front == rear+1) || (front+maxSize-1 == rear);         }                  // 큐가 꽉 찼는지 확인         public boolean full(){             return (rear == maxSize-1) || (front+maxSize-2 == rear);         }                  // 큐 rear에 데이터 등록         public void insert(Object item){                          if(full()) throw new ArrayIndexOutOfBoundsException();                          // rear 가 배열의 마지막이면 rear 포인터를 앞으로 돌린다.             if(rear == maxSize-1){                 rear = -1;             }             queueArray[++rear] = item;         }                  // 큐에서 front 데이터 조회         public Object peek(){                          if(empty()) throw new ArrayIndexOutOfBoundsException();                          return queueArray[front];         }                  // 큐에서 front 데이터 제거         public Object remove(){                          Object item = peek();             front++;                          // front의 다음 index가 배열크기+1 이면 처음으로 돌아간다             if(front==maxSize){                 front = 0;             }             return item;         } }

rear값이 배열의 마지막까지 갔을때 insert가 일어나면, 배열이 꽉차지 않았다면 rear 포인트를 배열의 제일 앞으로 돌려 index = 0  에 새로운 데이터를 삽입한다.

마찬가지로 큐에서 데이터가 제거될때, front 값이 배열 크기의 마지막 위치일때, front 를 index = 0 을 가리키도록 한다.

이렇게 rear와 front가 큐의 마지막 index에서 insert와 remove가 발생했을 때, 공백과 포화를 막기위해 최초 큐 배열 생성시에 인자로 받은 maxSize+1 크기의 배열을 생성해준다.

(배열의 마지막 공간은 임시공간이므로  데이터를 저장하는 큐의 크기는 maxSize-1 로 생각해야 된다는 것을 항상 기억하자)

원형 큐를 사용하면 배열 큐에서 발생한 문제점,  front, rear가 계속 증가하면서 rear가 꽉차면 더이상 insert가 불가능하거나, remove가 일어나면서 빠져나간 배열의 앞 공간의 메모리가 낭비된다는 문제점을 해결할 수 있다.

2. 우선순위 큐(Priority Queue)

우선순위 큐는 데이터의 우선순위에 따라 우선순위가 높은 데이터부터 꺼내도록 만들어진 큐이다.

데이터를 삽입할 때 우선순위에 따라서 정렬하여 삽입한 후 한쪽 방향에서만 데이터를 꺼내어 쓰도록 작성하면 된다.

스택과 큐도 데이터의 저장 시간에 따라 우선순위를 부여하는 우선순위 큐의 한 종류라고 할 수 있다.

스택은 가장 최근에 저장된 데이터의 우선순위가 높고 큐는 삽입한지 가장 오래된 데이터의 우선순위가 높은 구조로 작성된 우선순위 큐의 일종이 된다.

우선순위는 구현하는 어플리케이션의 비즈니스에 따라서 여러가지 기준이 될 수 있다.

예를들어 결재시스템을 구현할 때 결재할 문서들을 큐에 쌓을 경우 사안이 급한 문서에 우선순위를 높이 부여해 먼저 결재 처리를 하도록 한다던지 비행기 예약을 할때 출발시간이 얼마 남지 않은 항공편에 대해 우선순위를 높게 부여해 목록의 앞부분에 출력되게 한다던지 등의 기준을 고려해 볼 수 있을 것이다.

아래는 값이 작은 데이터에 우선순위를 높이 부여하는 예제이다.

public class PriorityQueue {              private int maxSize;         private long[] queueArray;         private int count;                      // 큐 배열 생성         public PriorityQueue(int maxSize){                              this.maxSize = maxSize;             this.queueArray = new long[maxSize];             this.count=0;                          }                          // 큐가 비어있는지 확인             public boolean empty(){                 return (count==0);             }                          // 큐가 꽉 찼는지 확인             public boolean full(){                 return (count==maxSize);             }                          // 큐에 데이터 등록             // 큐가 데이터가 큰 순서대로 배열의 앞에서부터 정렬되있기에             // 배열의 뒤에서부터 탐색하며 item 보다 큰 값이 있는 index 뒤에 삽입한다.             public void insert(long item){                                  if(full()) throw new ArrayIndexOutOfBoundsException();                                  if(empty()){                                          queueArray[count++] = item;                                  }else{                                          // 데이터의 뒤에서부터 앞으로 탐색한다.                     int i=0;                     for(i=count-1; i>=0; i--){                                                  // 현재 index의 데이터가 입력받은 데이터(item)보다 작으면 배열의 뒤로 밀어낸다.                         if(item > queueArray[i]){                                                          queueArray[i+1] = queueArray[i];                                                      }else{                             // item이 현재 index의 값보다 작으면 탐색을 멈춘다.                             // item 삽입 위치 확인                             break;                         }                     }                                          // item 등록                     queueArray[i+1] = item;                     count++;                 }             }                          // 큐의 마지막 데이터 조회 (가장작은 데이터)             public Object peek(){                                  if(empty()) throw new ArrayIndexOutOfBoundsException();                                  return queueArray[count-1];             }                          // 큐에서 마지막 데이터 제거 (가장작은 데이터)             public Object remove(){                                  Object item = peek();                 count--;                 return item;             } }

위의 예제는 데이터 값이 작은 순서대로 큐에서 빠져나가는 큐이다.

큐는 데이터가 큰 순서대로 정렬되어 있으며, peek()나 remove() 시에 배열의 가장 뒤(가장 작은 값)의 데이터를 제거한다.

데이터 insert 시에는 item이 들어갈 위치를 찾아야 하므로, 뒤에서 부터 탐색하면서 item 보다 큰 값이 나오면 그 뒤의 배열들을 뒤로 밀어내고 그자리에 item을 등록한다.

3. 데크 (Deque-double ended queue)

일반적인 큐는 데이터의 삽입과 삭제가 한쪽 방향에서만 발생하지만 데크는 리스트의 양쪽 끝 모두에서 데이터를 삽입, 삭제할 수 있도록 만들어진 특별한 형태의 자료구조이다.

양쪽 방향 모두에서 삽입과 삭제가 발생할 수 있으므로 큐나 스택으로 모두 활용 할 수 있다. 만약 한쪽 방향에서 삽입과 삭제를 모두 처리하면 스택으로 동작하는 것이고 한쪽 방향에서는 삽입만 발생하고 반대쪽 방향에서는 삭제만 발생하도록 처리하면 큐처럼 동작하게 된다.

Queue.zip

출처: https://hyeonstorage.tistory.com/264?category=578561 [개발이 하고 싶어요]