[자료구조] Java 큐(Queue) 정리 (배열, 연결리스트)

Java 큐(Queue) 정리 (배열, 연결리스트)

1. 큐(Queue)의 개요

큐(Queue)는 줄(line) 이라는 의미를 가지고 있다. 

큐(Queue)는 데이터의 제거는 대기 줄의 가장 앞에서 수행되며 데이터의 삽입은 대기 줄의 가장 뒤에서 수행이 되는 제한된 리스트 구조를 말하며 가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO - First In First Out) 형태의 자료구조이다.

가장 오래전에 입력된 데이터를 front 라고 하며 가장 최근에 입력된 데이터를 rear라고 한다. 데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어지기 때문에 큐를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나 front 노드와 rear 노드를 관리하는 연결 리스트를 이용할 수 있다.

2. 큐(Queue)의 동작

(1) 삽입 - insert

큐에 새로운 데이터를 삽입하는 작업을 insert라고 한다. 이는 리스트의 끝 부분을 가리키는 rear에서 발생하며 데이터가 삽입 될 때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

(2) 삭제(추출) - remove

큐에서 데이터를 제거하는 작업을 remove라고 하며 이는 항상 front에서 발생한다.

front가 가리키고 있는 데이터를 꺼낸 후 front 값을 하나 증가 시키도록 구현한다.

front 값이 rear를 추워랗게 되면 더이상 제거할 데이터가 없는 상태 즉, 자료가 하나도 없는 빈 큐임을 의미한다.

(3) 읽기 - Peek

큐에서 front가 가리키는 데이터를 읽는 작업을 peek라고 하며 데이터를 제거하지 않고 읽는 작업만 수행하므로 front 값을 변경시키지 않는다.

3. 배열을 이용한 큐 구현

public class ArrayQueue {          // 큐 배열은 front와 rear 그리고 maxSize를 가진다.     private int front;     private int rear;     private int maxSize;     private Object[] queueArray;          // 큐 배열 생성     public ArrayQueue(int maxSize){                  this.front = 0;         this.rear = -1;         this.maxSize = maxSize;         this.queueArray = new Object[maxSize];     }          // 큐가 비어있는지 확인     public boolean empty(){         return (front == rear+1);     }          // 큐가 꽉 찼는지 확인     public boolean full(){         return (rear == maxSize-1);     }          // 큐 rear에 데이터 등록     public void insert(Object item){                  if(full()) throw new ArrayIndexOutOfBoundsException();                  queueArray[++rear] = item;     }          // 큐에서 front 데이터 조회     public Object peek(){                  if(empty()) throw new ArrayIndexOutOfBoundsException();                  return queueArray[front];     }          // 큐에서 front 데이터 제거     public Object remove(){                  Object item = peek();         front++;         return item;     } }

가장 먼저 삽입한 데이터이며 데이터를 추출할 때 사용할 인덱스이기도 한 front 와 마지막에 삽입한  데이터의 인덱스를 가리키는 rear, 큐의 최대 크기인 maxSize와 실제 데이터를 저장할 배열인 queueArray를 선언하고 생성자를 통해 이를 초기화 한다.

empty() 메소드는 front가 rear를 추월했을 경우 더이상 꺼낼 데이터가 없으므로 true를 반환하며

full() 메소드는 데이터를 저장할 위치인 rear가 배열의 크기에 도달했을 때 true를 반환하여 배열이 다 찼음을 의미한다.

insert() 메소드는 리스트에 데이터를 삽입하는 메소드로 rear 값을 하나 증가시키고 배열의 rear 위치에 삽입할 데이터를 지정한다.

peek() 메소드는 리스트의 데이터 중 가장 먼저 삽입된 데이터를 가리키는 front에 위치한 데이터를 꺼내어 반환하며 

remove() 메소드는 peek() 메소드를 통해 데이터를 하나 반환하고 front를 하나 증가시키면서 데이터의 삭제(추출) 작업을 수행한다.

배열을 이용하여 큐를 구현할 때의 단점으로는 그 크기가 고정되었다는 점과 데이터의 삽입과 삭제가 반복 될 수록 rear와 front가 계속 증가되므로 이미 꺼낸 데이터가 들어있던 배열의 인덱스를 다시 활용할 수 없다는 점이다.

그리고 데이터가 다 차있지 않더라도 rear와 front가 계속 증가되다 보면 언젠가는 배열의 사이즈까지 도달하여 더이상 사용할 수 없게 된다는  문제점이 발생한다.

이러한 문제점을 해결하기 위하여 이동 큐(moving queue)를 사용할 수 있는데 이는 큐가 다 찼을 경우 앞부분에 사용할 수 있는 공간만큼 전체 데이터들을 앞쪽으로 이동시키고 rear와 front를 수정하여 남은 공간을 사용하는 방법이다.

하지만 자료를 이동하면서 발생하는 시간을 고려해 보면 효율적이지 않다는 것을 알 수 있다.

최악의 경우 남은 공간이 하나밖에 없을 경우 하나의 데이터를 큐에 넣기 위해 매번 maxSize-1 만큼의 데이터를 이동시켜야 할 수도 있기 때문이다.

이를 보완하기 위해 원형 큐(Circular Queue)를 사용할 수 있다.

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

Queue를 구현하기 위한 효과적인 방법도 대부분의 경우 연결 리스트를 이용하는 방법이다.

4. 연결 리스트를 이용한 큐의 구현

연결 리스트를 이용하여 큐를 구현할 경우 데이터가 저장될 큐의 크기를 미리 지정하지 않아도 되며 배열처럼 front 보다 작은 인덱스 공간(삭제한 공간)을 낭비하지 않아도 된다는 장점을 가지고 있다.

public class ListQueue {          private class Node{                  // 노드는 data와 다음 노드를 가진다.         private Object  data;         private Node nextNode;              Node(Object data){             this.data = data;             this.nextNode = null;         }     }          // 큐는 front노드와 rear노드를 가진다.     private Node front;     private Node rear;          public ListQueue(){         this.front = null;         this.rear = null;     }          // 큐가 비어있는지 확인     public boolean empty(){         return (front==null);     }          // item을 큐의 rear에 넣는다.     public void insert(Object item){                  Node node = new Node(item);         node.nextNode = null;                  if(empty()){                          rear = node;             front = node;                  }else{                          rear.nextNode = node;             rear = node;                      }     }          // front 의 데이터를 반환한다.     public Object peek(){         if(empty()) throw new ArrayIndexOutOfBoundsException();         return front.data;     }          // front 를 큐에서 제거한다.     public Object remove(){                  Object item = peek();         front = front.nextNode;                  if(front == null){             rear = null;         }                  return item;     } }

front 노드는 리스트 중 가장 먼저 삽입한 노드이며 데이터를 삭제하거나 꺼낼 노드를 의미하고

rear 노드는 가장 최근에 삽입한 노드를 의미한다.

front와 rear의 초기값은 null 이고 front가 null 값을 가질 경우 더이상 꺼낼 데이터가 없다는 의미이다.

데이터를 한 건 삽입 할 경우에는 노드를 먼저 생성 한 후 생성한 노드의 nextNode 값을 null로 지정하여 마지막 노드임을 표시하고 비어있는 큐였을 경우 front와 rear 값 모두 새로 생성한 노드를 지정하도록 한다.

만약 비어있지 않고 데이터가 있었을 경우에는 삽입하기 이전의 rear 노드의 nextNode 값을 새로운 노드를 가리키도록 지정하고 새로운 노드가 이제 rear 노드가 된다.

데이터를 꺼낼 때에는 가장 오래된 노드인 front 노드의 data를 반환하도록 peek() 메소도를 작성한다.

remove() 메소드는 front 노드를 삭제하고 반환하면 되는데 peek()를 호출하여 front 노드의 data를 반환하고 삭제될 노드의 nextNode가 새로운 front 노드가 된다.

만약 삭제한 노드가 마지막 노드였을 경우 큐에 더이상 데이터가 없으므로 rear 값도 초기화 시킨다.

Queue.zip

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