Binaryseop
[자료구조] 연결 큐(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();
}
}
· 실행 결과
'자료구조' 카테고리의 다른 글
[자료구조] 이진 트리(Binary Tree) 개념과 구현 (3) | 2021.10.30 |
---|---|
[자료구조] 덱(Deque, Double-ended Queue) 설명 및 구현 (0) | 2021.10.30 |
[자료구조] 원형 큐(Circular Queue) 설명 및 구현 (0) | 2021.10.28 |
[자료구조] 큐(Queue) 설명 및 구현 (0) | 2021.10.28 |
[자료구조] 연결 리스트를 이용하여 스택(Stack) 구현 (0) | 2021.10.27 |