1. Queue란?
- 먼저 들어온 데이터가 먼저 나간다. 즉, 선입선출(FIFO) 방식이다.
- 맨 앞의 원소에만 접근이 가능하다.
cf) 연결리스트로 큐 구현하기
연결 리스트로 큐를 구현할 때는 tail에 큐의 마지막 노드를 저장하고 tail이 next로 큐의 첫 번째 값을 참조하게 한다.
2. Queue 구현하기
구현할 내용은 아래와 같다.
- enqueue(E x) - 원소 x를 큐의 끝에 추가한다.
- dequeue() - 큐의 가장 앞에 있는 원소를 삭제한다.
- front() - 큐의 가장 앞에 있는 원소를 리턴한다.
- isEmpty() - 큐가 비어있으면 true, 그렇지 않으면 false를 리턴한다.
- dequeueAll() - 큐에 있는 모든 원소를 삭제한다.
- printAll() - 큐의 모든 원소를 순서대로 출력한다.
** 원래 큐에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.
1) 노드 클래스
public class Node<E> {
public E item;
public Node<E> next;
public Node (E newItem) {
item = newItem;
next = null;
}
public Node (E newItem, Node<E> nextNode) {
item = newItem;
next = nextNode;
}
}- item 변수에 데이터를 저장한다.
- next 변수에 다음 노드를 저장한다. next는 다음 노드의 위치를 가리키는 포인터가 된다.
- 첫 번째 생성자는 데이터를 입력받아 데이터를 item에 저장하고, 포인터 값은 null로 저장한다.
- 두 번째 생성자는 데이터와 다음 노드를 입력받아 데이터를 item에 저장하고, 포인터 값에 다음 노드를 저장한다.
2) 인터페이스
public interface QueueInterface<E> {
public void enqueue(E x);
public void dequeue();
public E front();
public boolean isEmpty();
public void dequeueAll();
public void printAll();
}
3) LinkedQueue 클래스
- 필드 & 생성자 영역
//필드 영역
private Node<E> tail;
int size=0;
//생성자 영역
public LinkedQueue() {
tail=null;
}- tail - 큐의 가장 끝 노드를 저장한다. (최근에 들어온 값)
- size - 큐 원소의 개수를 저장한다.
- 생성자 - tail에 null 값을 할당한다.
** 사실 위 메서드 중 printAll을 구현하지 않는다면 size는 필요하지 않다.
- 메서드 영역
<enqueue 메서드 구현>
@Override
public void enqueue(E x) {
Node<E> newNode = new Node<>(x);
if (isEmpty()) {
tail = newNode;
tail.next=tail;
} else {
newNode.next=tail.next;
tail.next=newNode;
tail=newNode;
}
size++;
}- 입력 받은 값 x를 가지는 새 노드를 생성한다.
- 만약 첫 노드라면 tail에 newNode를 입력하고 tail이 next로 스스로를 참조하게 한다.
- 그렇지 않다면 새 노드가 front를 참조하고, tail이 새 노드를 참조하게 한다.
- tail 값에 newNode를 입력한다.
<dequeue 메서드 구현>
@Override
public void dequeue() {
if (isEmpty()) {
System.out.println("ERROR");
} else {
if (tail.next==tail) {
tail = null;
} else {
tail.next=tail.next.next;
}
}
size--;
}- 만약 큐가 비어 있다면 에러를 출력한다.
- 만약 큐에 원소가 한 개라면 tail 값에 null을 입력한다.
- 큐에 원소가 여러 개라면 tail이 next로 기존 front값을 생략하고 그 다음 노드를 참조하게 한다.
<front 메서드 구현>
@Override
public E front() {
if (isEmpty()) {
return null;
} else {
return tail.next.item;
}
}- 만약 큐가 비어 있다면 null을 리턴한다.
- 그렇지 않다면 front의 item값을 출력한다.
<isEmpty 메서드 구현>
@Override
public boolean isEmpty() {
return (tail==null);
}- tail==null 이면 true, 아니면 false를 리턴한다.
<dequeueAll 메서드 구현>
@Override
public void dequeueAll() {
tail=null;
size=0;
}- tail과 size를 초기화한다.
<printAll 메서드 구현>
@Override
public void printAll() {
Node<E> currNode=tail;
for (int i=0; i<size; i++) {
currNode=currNode.next;
System.out.print(currNode.item+" ");
}
}- front부터 size만큼 큐를 순회하며 해당 노드의 item값을 출력한다.
- 전체 코드
public class LinkedQueue<E> implements QueueInterface<E> {
//필드 영역
private Node<E> tail;
int size=0;
//생성자 영역
public LinkedQueue() {
tail=null;
}
//메서드 영역
@Override
public void enqueue(E x) {
Node<E> newNode = new Node<>(x);
if (isEmpty()) {
tail = newNode;
tail.next=tail;
} else {
newNode.next=tail.next;
tail.next=newNode;
tail=newNode;
}
size++;
}
@Override
public void dequeue() {
if (isEmpty()) {
System.out.println("ERROR");
} else {
if (tail.next==tail) {
tail = null;
} else {
tail.next=tail.next.next;
}
}
size--;
}
@Override
public E front() {
if (isEmpty()) {
return null;
} else {
return tail.next.item;
}
}
@Override
public boolean isEmpty() {
return (tail==null);
}
@Override
public void dequeueAll() {
tail=null;
size=0;
}
@Override
public void printAll() {
Node<E> currNode=tail;
for (int i=0; i<size; i++) {
currNode=currNode.next;
System.out.print(currNode.item+" ");
}
}
}
3) 결과 확인하기
<코드>
public class Test {
public static void main(String[] args) {
LinkedQueue<Integer> lst = new LinkedQueue<>();
lst.enqueue(100);
lst.enqueue(200);
lst.enqueue(300);
lst.enqueue(400);
lst.printAll();
System.out.println();
//LinkedQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
System.out.println(lst.front());
//LinkedQueue의 가장 앞에 있는 값을 출력
lst.dequeue();
lst.printAll();
System.out.println();
//LinkedQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
System.out.println(lst.isEmpty());
//LinkedQueue가 비었는지 출력
}
}<결과>
'자료구조' 카테고리의 다른 글
| [Java] 힙(Heap) 배열로 구현하기 (0) | 2022.08.06 |
|---|---|
| [Java] 큐(Queue) 배열로 구현하기 (0) | 2022.08.01 |
| [Java] 스택(Stack) 연결 리스트로 구현하기 (0) | 2022.07.30 |
| [Java] 스택(Stack) 배열로 구현하기 (0) | 2022.07.30 |
| [Java] 원형 양방향 연결 리스트 (CircularDoublyLinkedList) 구현하기 (0) | 2022.07.29 |
