[자료구조] 연결 큐(Linked Queue) 설명 및 구현

1. 연결 큐

순차 자료구조 방식을 이용한 선형 큐(Linear Queue)와 원형 큐(Circular Queue)는 몇 가지 문제가 있습니다.

 

첫 째, 사용 크기가 제한되어 큐의 길이를 마음대로 변경할 수 없습니다.

 

둘 째, 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리 낭비가 있습니다.

 

이와 같은 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기가 제한없는 연결 큐(Linked Queue)를 사용합니다.

2. 연결 큐 알고리즘

연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째 노드를 가리키는 참조변수 front와 마지막 노드를 가리키는 참조변수 rear를 사용합니다.

· 연결 큐 생성

createLinkedQueue()
    front ← null;
    rear ← null;
end createLinkedQueue()

새로 생성한 공백의 연결 큐는 front와 rear의 초기값을 null로 설정합니다.

· 공백 상태 검사

isEmpty(lQ){
    if(front = null) then return true;
    else return false;
end isEmpty()

연결 큐가 공백 상태인 경우는 연결된 노드가 하나도 없을 경우입니다. 따라서 front의 값이 null인 경우 연결 큐의 공백 여부를 알 수 있습니다.

· 삽입 알고리즘

enQueue(lQ, item)
    new ← getNode();
    new.data ← item;
    new.link ← null;
    if(isEmpty(lQ)) then {	// ①
        rear ← new;
        front ← new;
    }
    else{			// ②
         rear.link ← new;
         rear ← new;
    }
end enQueue()

삽입할 새 노드를 생성하여 데이터 필드에 item을 저장하고 마지막 위치에 노드가 삽입되므로 링크 필드에 null을 저장합니다.

 

① 연결 큐가 공백일 경우, 삽입할 새 노드가 첫 번째 노드이자 마지막 노드이므로 front와 rear가 모두 새 노드를 가리키게 합니다.

 

② 연결 큐가 공백이 아닌 경우, 연결 큐의 마지막 노드 뒤에 새 노드를 삽입합니다. 그리고 rear가 마지막 노드를 참조하도록 합니다.

· 삭제 알고리즘

deQueue(lQ)
    if(isEmpty()) then empty();
    else{
        item ← front.data;
        front ← front.link;                // ①
        if(isEmpty()) then rear ← null;    // ②
        return item;
    }
end deQueue()

① 삭제 연산 후에 front는 다음 노드를 가리켜야 하므로 front에 다음 노드의 주소인 front.link 값을 저장합니다.

 

② 현재 연켤 큐에 노드가 하나뿐이어서 재설정한 front가 null이 되는 경우에는 삭제 연산 후에 공백 큐가 되므로 rear를 null로 설정합니다.

· 연결 큐 구현

· Queue

public interface Queue {
	boolean isEmpty();
	void enQueue(char data);
	char deQueue();
	char peek();
	void delete();
}

 

· QueueNode

public class QueueNode {
	private char data; // 데이터 필드
	public QueueNode link; // 링크 필드

	public QueueNode(char data) {
		this.data = data;
		this.link = null;
	}

	public char getData() {
		return this.data;
	}
}

 

· LinkedQueue

public class LinkedQueue implements Queue {
	private QueueNode front;
	private QueueNode rear;

	// 연결 큐 초기화
	public LinkedQueue() {
		this.front = null;
		this.rear = null;
	}

	@Override
	public boolean isEmpty() {
		return (front == null); // front가 null이면 공백상
	}

	@Override
	public void enQueue(char data) {
		QueueNode newNode = new QueueNode(data);

		if (isEmpty()) { // 연결 큐에 노드가 없을 경우
			front = newNode;
			rear = newNode;
		} else { // 연결 큐에 노드가 있는 경우
			rear.link = newNode;
			rear = newNode;
		}
	}

	@Override
	public char deQueue() {
		if (isEmpty()) {
			System.out.println("연결 큐가 공백상태입니다.");
			return 0;
		} else {
			char data = front.getData();
			front = front.link;
			if (front == null) { // 연결 큐가 공백상태가 되는 경우
				rear = null;
			}
			return data;
		}
	}

	@Override
	public char peek() {
		if (isEmpty()) {
			System.out.println("연결 큐가 공백상태입니다.");
			return 0;
		} else {
			return front.getData(); // front 위치의 데이터를 반환
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			System.out.println("연결 큐가 공백상태입니다.");
		} else {
			front = front.link;
			if (front == null) { // 연결 큐가 공백상태가 되는 경우
				rear = null;
			}
		}
	}

	// 연결 큐 출력
	public void printQueue() {
		if (isEmpty()) {
			System.out.println("연결 큐가 공백상태입니다.");
		} else {
			QueueNode temp = front;
			System.out.printf("Q = ");
			while (temp != null) {
				System.out.printf("%c ", temp.getData());
				temp = temp.link;
			}
			System.out.println("\n");
		}
	}
}

 

· MainForLinkedQueue

public class MainForLinkedQueue {
	public static void main(String[] args) {
		LinkedQueue q = new LinkedQueue();
		char data = 0;

		System.out.println("1. 연결 큐에 원소 4개 삽입하기");
		for (char c = 'A'; c <= 'D'; c++) {
			q.enQueue(c);
		}
		q.printQueue();

		System.out.println("2. 가장 먼저 들어온 값 반환하기");
		data = q.peek();
		System.out.printf("%c\n\n", data);

		System.out.println("3. 연결 큐의 원소 3개 디큐");
		for (int i = 0; i < 3; i++) {
			data = q.deQueue();
			System.out.printf("삭제된 원소: %c\n", data);
			q.printQueue();
		}

		System.out.println("4. 원소 1개 삭제하기");
		q.delete();
		q.printQueue();
	}
}

 

· 실행 결과