자료구조: 2-3. Queue 구현

지난 챕터에 이어서, 큐를 연결리스트와 배열로 구현해보도록 하겠다.

1. 배열을 이용한 원형 큐 구현

스택과 다르게, 큐를 배열으로 구현하면 오버헤드가 발생할 수 있다. 왜냐하면 데이터의 출입구가 통일되어있지 않기 때문이다. 데이터는 뒤로 들어왔는데, 앞으로 나가야한다면?
앞으로 나간 데이터가 상주하던 공간을 채우기 위해서 뒤에서 기다리는 데이터들을 한칸씩 앞으로 이동시켜야한다. 삭제 시에도 마찬가지이다. 따라서 이 문제를 상쇄시킬 수 있는 '원형 큐'를 구현해보도록 하겠다.

public class CircleQueue {
	//섹션1.
	int front = 0;
	int rear = 0;
	Object[] queue;
	
	public CircleQueue(int size) {
		this.queue = new Object[size]; 
	}
	
	//섹션2.
	boolean isFull() {
		return this.queue[rear] != null;
	}
	
	boolean isEmpty() {
		return front == rear;
	}
	
	//섹션3.
	void add(Object data) {
		if (this.isFull()) {
			throw new RuntimeException("큐 찼다.");
		}
		this.queue[rear] = data;
		++rear;
		rear = rear % this.queue.length;
	}
	
	//섹션4.
	Object poll() {
		if (this.isEmpty()) {
			throw new RuntimeException("큐 비었다. 이 자식아.");
		}
		Object returnData = this.queue[front];
		++front;
		front = front % this.queue.length;
		return returnData;
	}
	
	//섹션5.
	Object peek() {
		return this.queue[front];
	}

Section.1 인스턴스 변수

데이터의 위치를 가르킬 변수 2개를 생성해야한다.
하나는 첫번째 위치(데이터가 빠져나가는 위치)를 가르키는 front 변수, 마지막 위치(데이터가 들어오는 위치)를 가르키는 rear변수를 만들도록 하겠다.

Section.2 큐 상태 조회

큐가 비어있는지, 가득 차있는지 체크해야한다. 배열로 큐를 구현했기 때문이다.

• isFull()은 큐의 입구인 rear가 가르키는 공간이 null이 가득 차있는 것으로 간주한다.
• isEmpty()는 큐의 출구인 front가 가르키는 공간이 rear가 가르키는 공간과 같으면 큐가 비어있는 것으로 간주한다. 초기에 front와 rear는 0으로 초기화되있고, 추후에 데이터가 다 빠져나가면 서로 값이 같아진다. 이때 우리는 큐가 비어있는 걸로 알게되는 것이다.

Section.3 데이터 삽입

이 메소드를 보자마자, mod 연산이 들어간 마지막 코드를 볼 수 있을 것이다. 그렇다. 이것이 원형 큐의 특성이다. 배열로 구현을 하면, 공간이 한정적이다. 만약 rear가 배열의 맨 마지막 인덱스를 가르키고 있는데, 이때 삽입이 발생한다면? OverFlow가 발생하게 될 것이다.
따라서, 큐에 만약 공간이 있다면, rear를 맨 끝 인덱스에서 다시 맨 처음 인덱스를 가르키게 바꿔야한다. 공간이 남아있다면, 구조 상 인덱스 0인 공간은 front가 가르키고 있지 않고, 비어있기 때문이다.
이렇게 rear가 가르키는 공간을 다시 처음으로 초기화하면서 '원형처럼 공간이 이루어져 있을 것이다' 라고 생각하게 되는 것이다. 로직 순서는 아래와 같다.

1. 큐가 가득 차 있으면, 예외를 발생시킨다.
2. rear가 가르키는 공간에 데이터를 삽입한다.
3. rear값을 +1 시킨다.
4. 갱신된 rear값을 큐의 길이만큼 나누고, 나머지 값을 rear값으로 다시 채워넣는다.
   -> 재갱신된 rear값은 이제 인덱스 범위를 넘어서지 않게 된다.

Section.4 데이터 삭제

데이터 삽입 시에는 rear값을 조작하면서 Overflow가 발생하지 않도록 설정했다. 삭제 시에는 front 값을 조작해야한다. front도 이동하는 객체로 간주되기 때문에, 데이터들이 빠져나가다보면 언제든지 맨 끝 칸에 다다를 수 있기 때문이다. 로직 순서는 아래와 같다.

1. 큐가 비어있다면, 데이터를 삭제시킬 수 없으므로 예외를 발생시킨다.
2. 삭제시킬 데이터를 임시변수에 잠시 저장한다.
3. front값을 갱신 (+1)
4. front값에 대해 삽입 때와 마찬가지로 mod연산을 수행하여 다음으로 빠져나갈 데이터의 위치를 올바르게 가르키도록 설정한다.
5. 삭제 데이터를 잠시 보관해둔 임시변수 반환!

Section.5 데이터 조회

굳이 설명할 필요가 없다. 앞에서 말했던대로 front는 빠져나갈 데이터를 가르키는 인덱스를 보관하는 변수이다.
따라서 front 위치의 데이터를 반환하면 된다.

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

//섹션1.
class QNode {
	Object data;
	QNode next;
}

public class ListQueue {
	//섹션2.
	QNode front = null;
	QNode rear = null;
	int size = 0;
	
	//섹션3.
	boolean isEmpty() {
		return (front == null && rear == null);
	}
    
    int size() {
    	return this.size;
    }
	
	//섹션4.
	void add(Object data) {
		QNode newNode = new QNode();
		newNode.data = data;
		
		if (front == null && rear == null) {
			//최초 삽입
			front = newNode;
			rear = newNode;
		} else {
			//최초 삽입 아니면
			rear.next = newNode;
			rear = newNode;
		}
		++size;
	}
	
	//섹션5.
	Object poll() {
		//원소가 아예 없으면 예외 던지기
		if (this.isEmpty()) {
			throw new RuntimeException("큐에 원소가 없다. ㄲㅈ");
		}
		
		//원소 삭제
		QNode pollNode = front;
		Object returnData = pollNode.data;
		front = pollNode.next;
		
		if (pollNode == rear) {
			rear = null;
		}
		
		--size;
		return returnData;
	}
	
	//섹션6.
	Object peek() {
		return front.data;
	}

Section.1 기본 자료구조

스택 구현 때와 마찬가지로 연결리스트를 활용하여 구현해야하니 노드를 만들 기본 자료구조를 생성해야한다.
노드 안에 담을 데이터와 다음 노드의 주소를 담을 next영역을 멤버변수로 선언한다.

Section.2 인스턴스 변수
배열 구현 때와 마찬가지로 첫 데이터와 마지막 데이터를 참조할 front와 rear변수가 필요하다. front는 큐의 출구에서 가장 가까운 노드를 참조하고, rear는 큐의 입구에서 가장 가까운 노드를 참조한다. size변수는 노드가 삽입 혹은 삭제될 때 갱신될 변수이다. 현재 큐의 크기를 담고 있다.

Section.3 큐 상태 조회

• isEmpty() 큐가 비어있는지 확인하는 함수. rear과 front가 null이면 큐가 비어있다고 간주한다.
• size() 큐의 크기를 출력하는 함수.

Section.4 노드 삽입

front와 rear의 위치를 조정하는 작업이 제일 중요하다. 또한 조건에 따라서 rear와 front에 들어갈 내용이 달라진다. 주요 조건은 2가지이다.

• 최초삽입
• 최초삽입이 아닌 경우

로직은 아래에 기술한 순서와 같다.

1. 새로운 노드를 생성하고, data영역에 매개변수로 들어온 데이터를 넣어둔다.
2. 최초삽입인 경우, front와 rear은 null로 초기화되어 있을 것이다. 따라서 front와 rear에
   새로 생성한 노드의 참조값을 저장한다.
3. 최초삽입이 아닌 경우, rear값만 조정하면 된다. front는 이미 빠져나갈 예정인 데이터의 참조값을 지니고 있다. rear는 큐의 입구라서, add() 수행마다 참조값을 변경해줘야한다.
   원래 rear에 걸려있던 노드의 next영역을 새로운 노드의 참조값으로 채워준다. 그리고 rear를 새로 어온 노드와 연결한다.
4. 마지막으로 size변수를 +1 시켜준다. 노드가 추가되면, 큐의 크기는 +1이 되야하기 때문이다.

Section.5 노드 삭제

삭제 방식은 삽입과 조금 다르다. 원리를 이해하는 것이 중요하다.
우선 제시되는 조건은 아래와 같다.

• 1. 노드가 1개만 남은 경우 어떻게 삭제할 것인가?
• 2. 노드가 여러 개인 경우 어떻게 삭제할 것인가?

하지만 위의 조건들에 대응하는 조건문을 일일히 만들 필요는 없다.

//섹션5 코드 중 일부...
		//(1) 1개 밖에 안남았던, 여러 개가 남았던 일단 front를 삭제시킬 노드의 다음 노드와 연결한다. 
		front = pollNode.next; 
        
		if (pollNode == rear) {
        //(2) pollNode가 rear과 같다면, rear를 null로 갱신
			rear = null;
		}

(1)의 과정에서 front를 null로 바꾸는 과정을 필요없다. 왜냐? 만약 노드가 하나씩
poll()되고 있다고 가정해보자. 순차적으로 노드가 빠져나가서 이제 딱 1개 밖에 안남았다.
지금과 같이 노드가 한 개 밖에 안남았다면, pollNode의 next엔 null이 저장되어 있기 때문이다.
애초에 다음 노드가 없기 때문에, pollNode의 next는 애시당초 null이었을테고, front를 pollNode.next로 갱신하면 알아서 null값이 채워진다.
(2)의 과정은 pollNode가 rear였다면, 어떻게 처리할건지에 대해 작성되어있다.
노드가 한 개 남은 상황에서 (1)에 걸려서 노드가 제거가 되었다면, rear 역시 null로 갱신해야한다. 따라서 pollNode가 rear이면, rear은 null로 갱신된 것이다.

Section.6 노드 조회

데이터의 출구를 front가 가르키고 있다. 따라서 front가 참조하고 있는 노드를 반환시켜주면 된다.