* 큐 (Queue)
"스택과 달리 한쪽 끝에서는 삽입 작업이, 반대쪽 끝에서는 삭제 작업이 이루어진다."
따라서, 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out)의 구조로 운영된다.
줄을 서있다가 순서대로 앞에서부터 입장하는 줄서기도 큐의 선입선출 구조의 예가 될 수 있다.
큐는 한쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하도록 하고, 가장 먼저 큐에 들어온 첫번째 원소이며,
다른 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한하고, 큐에 가장 늦게 들어온 마지막 원소이다.
큐는 다음과 같이 다섯가지의 기능을 구현해야 한다.
(1) 공백 큐 생성 (createQueue) - 초기 상태의 공백큐는 저장된 원소가 없으므로 front와 rear를 -1로 설정한다.
(2) 큐가 공백인지 아닌지 확인 (isEmpty)
(3) 큐의 rear에 원소를 삽입하는 삽입연산 (enQueue)
(4) 큐의 front에 원소 삭제하고 반환하는 연산 (deQueue)
(5) 큐의 front에 있는 원소를 삭제하는 연산 (peek)
* 큐 (Queue) - 연결큐
- 순차 자료구조 방식은 사용 크기가 제한되어 있어 큐를 마음대로 변경할 수 없고, 원소가 없을 때도 크기를 유지하므로 메모리가 낭비된다. 이와 같은 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기에 제한이 없도록 한다.
- 첫번째 노드를 가리키는 참조변수 front 와 마지막 노드를 가리키는 참조변수 rear 를 사용한다.
- 초기 상태(공백 큐)는 front와 rear를 널(NULL)로 설정하여 표현한다.
QueueNode.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
package Queue;
public class QueueNode {
char item;
QueueNode next;
public QueueNode() {
this.next = null;
}
public QueueNode(char item){
this.item = item;
next = null;
}
public char getItem(){
return this.item;
}
} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 |
package Queue;
public class LinkedQueue implements Queue{
private QueueNode front;
private QueueNode rear;
public LinkedQueue() {
front = null;
rear = null;
}
@Override
public boolean isEmpty() {
return (front==null);
}
@Override
public void enQueue(char item) {
QueueNode node = new QueueNode(item);
if(isEmpty()){
front = node;
rear = node;
}else{
rear.next = node;
rear = node;
}
}
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("큐의 내용이 존재하지 않습니다.");
return 0;
}else{
char item = front.item;
front = front.next;
if(front==null){
rear=null;
}
return item;
}
}
@Override
public void delete() {
if(isEmpty()){
System.out.println("큐의 내용이 존재하지 않습니다.");
}else{
front = front.next;
if(front==null){
rear=null;
}
}
}
@Override
public char peek() {
if(isEmpty()){
System.out.println("큐의 내용이 존재하지 않습니다.");
return 0;
}else{
return front.item;
}
}
public void print() {
if(isEmpty()){
System.out.println("큐의 내용이 존재하지 않습니다.");
}else{
QueueNode node = front;
while(node!=null){
System.out.print(node.item + " ");
node = node.next;
}
System.out.println();
}
}
} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 |
package Queue;
public class LinkedTest {
public static void main(String[] args) {
char deletedItem;
LinkedQueue queue = new LinkedQueue();
queue.enQueue('A');
queue.print();
queue.enQueue('B');
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deletedItem : " + deletedItem);
}
queue.print();
queue.enQueue('C');
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deletedItem : " + deletedItem);
}
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deletedItem : " + deletedItem);
}
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deletedItem : " + deletedItem);
}
queue.print();
}
} |
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 트리 (Tree) (0) | 2015.11.05 |
|---|---|
| [자료구조/java] 덱 (Deque) - 연결 자료구조 방식 구현 (0) | 2015.11.04 |
| [자료구조/java] 큐 (Queue) - 선형큐, 원형큐 순차 자료구조 방식 구현 (0) | 2015.11.03 |
| [자료구조/java] 수식의 표기법 - Stack 사용 (1) | 2015.11.02 |
| [자료구조/java] 스택의 응용 - 수식의 괄호 검사 (java) (0) | 2015.10.31 |
