큐(Queue)
1. 큐(Queue)
- 큐는 자료 구조에 들어있는 요소 중에서 가장 먼저 삽입한 요소를 꺼냄.
- enqueue는 요소를 큐에 삽입
- dequeue는 요소를 큐에서 가장 먼저 삽입한 요소를 꺼냄
- 먼저 삽입된 요소부터 순서대로 꺼내는 규칙을 FIFO(first-in first-out)라고 함
2. 큐(Queue) 구현
2.1 큐(Queue) Interface
public interface Queue<T> {
// 큐(Queue)에 Node 삽입
void enqueue(T value);
// 큐(Queue)의 사이즈를 반환
int size();
// 큐(Queue)가 비어있는지 true/false 반환
boolean isEmpty();
// 큐(Queue)의 첫번째 Node의 값을 반환하고 Node를 삭제
T dequeue();
// 큐(Queue)의 첫번재 Node의 값을 반환
T peek();
// 입력받은 값이 큐(Queue)에 존재하는지 true/false를 반환
boolean contains(T string);
}
2.2 큐(Queue)의 메소드 구현
2.2.1 큐의 Node 정의
// Queue의 Node를 정의
private static class Node<T>{
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}2.2.2 enqueque() 메소드 구현
// 큐에 Node를 삽입하는 메소드
@Override
public void enqueue(T value) {
Node<T> newNode = new Node<T>(value);
if(isEmpty()) {
front = newNode;
rear = newNode;
}else {
rear.next = newNode;
rear = newNode;
}
size++;
}2.2.3 size() 메소드 구현
// 큐의 size를 반환하는 메소드
@Override
public int size() {
return size;
}2.2.4 isEmpty() 메소드 구현
// queue가 비어있으면 true를 반환, 비어있지 않으면 false를 반환하는 메소드
@Override
public boolean isEmpty() {
return (this.size == 0);
}2.2.5 dequeue() 메소드 구현
// 큐의 첫번째 Node의 값을 반환하고 Node를 삭제하는 메소드
@Override
public T dequeue() {
if(isEmpty()) {
throw new RuntimeException("스택이 비어있습니다.");
}else {
Node<T> deNode = front;
front = front.next;
size--;
return deNode.data;
}
}2.2.5 peek() 메소드 구현
// 큐의 첫번째 Node의 값을 반환하는 메소드
@Override
public T peek() {
if(isEmpty()) {
throw new RuntimeException("스택이 비어있습니다.");
}
return front.data;
}2.2.6 contains() 메소드 구현
// 입력받은 값이 큐에 존재하면 true, 존재하지 않으면 false를 반환하는 메소드
@Override
public boolean contains(T string) {
Node<T> current = front;
while(current != null) {
if(current.data.equals(string)) {
return true;
}
current = current.next;
}
return false;
}2.2.7 toString() 메소드 구
// 큐에 존재하는 모든 Node의 값을 출력하는 메소드
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<T> current = front;
sb.append("[");
while(current != null) {
sb.append(current.data + ", ");
current = current.next;
}
if(sb.lastIndexOf(",") != -1) {
sb.replace(sb.lastIndexOf(","), sb.length(), "]");
}else {
sb.append("]");
}
return sb.toString();
}3. 큐(Queue) 테스트
3.1 size() & isEmpty() 테스트
// 큐 생성 후, size()메소드와 isEmpty()메소드 테스트
Queue<String> queue = new ArrayListQueue<>(5);
System.out.println(queue);
System.out.println(queue.size());
System.out.println(queue.isEmpty());
3.2 enqueue() 테스트
// enqueue() 테스트
queue.enqueue("딸기");
queue.enqueue("포도");
queue.enqueue("망고");
queue.enqueue("수박");
queue.enqueue("사과");
System.out.println(queue);
System.out.println(queue.size()); // Node가 5개 삽입되었기 때문에 5를 반환
System.out.println(queue.isEmpty()); // Node가 삽입되었기 때문에 false를 반환
3.3 dequeue() 테스트
// dequeue() 테스트
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue);
System.out.println(queue.size()); // Node 2개를 삭제했기 때문에 3을 반환
System.out.println(queue.isEmpty());
3.4 peek() 테스트
// peek() 테스트
System.out.println(queue.peek());
System.out.println(queue);
System.out.println(queue.size()); //peek()는 Node의 값만 반환하고 삭제하지 않기 때문에 3을 반환
System.out.println(queue.isEmpty());
3.5 contains() 테스트
// contains() 테스트
System.out.println(queue);
System.out.println(queue.contains("망고")); // true를 반환
System.out.println(queue.contains("딸기")); // false를 반환
'자료구조' 카테고리의 다른 글
| [자료구조] 그래프(Graph) (0) | 2024.06.28 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2024.06.28 |
| [자료구조] 해시 테이블(Hash Table) (0) | 2024.06.28 |
| [자료 구조] 스택(Stack) (0) | 2024.06.20 |
| [자료구조]배열(Array)과 연결 리스트(Linked List) (0) | 2024.06.20 |
