* 큐 (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) - 선형큐
- 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현.
- "배열의 크기 = 큐의 크기" → 즉, 큐에 저장할 수 있는 최대 원소의 갯수.
- 초기 공백 큐의 상태는 front 변수와 rear 변수의 값을 -1로 설정.
ArrayQueue.java
|
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
81
82 |
package Queue;
public class ArrayQueue implements Queue {
private int front;
private int rear;
private int queueSize;
private char itemArray[];
//생성자(큐 생성)
public ArrayQueue(int queueSize){
front = -1;
rear = -1;
this.queueSize = queueSize;
itemArray = new char[this.queueSize];
}
//큐가 비어있는지 확인
@Override
public boolean isEmpty() {
return (front==rear);
}
//큐가 가득 차있는지 확인
public boolean isFull() {
return (rear==queueSize-1);
}
//큐의 삽입 연산
@Override
public void enQueue(char item) {
if(isFull()){
System.out.println("큐가 꽉 찼습니다.");
}else{
itemArray[++rear] = item;
}
}
//큐의 삭제 및 반환 연산
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("큐가 비었습니다.");
return 0;
}else{
return itemArray[++front];
}
}
//큐 삭제
@Override
public void delete() {
if(isEmpty()){
System.out.println("큐가 비었습니다.");
}else{
++front;
}
}
//현재 큐의 맨 앞의 값
@Override
public char peek() {
if(isEmpty()){
System.out.println("큐가 비었습니다.");
return 0;
}else{
return itemArray[front+1];
}
}
//전체 큐 출력
public void printQueue(){
if(isEmpty()){
System.out.println("큐가 비었습니다.");
}else{
for(int i=front+1; i<=rear; i++){
System.out.print(itemArray[i] + " ");
}
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 |
package Queue;
public class ArrayTest {
public static void main(String[] args) {
int queueSize = 3;
char deletedItem;
ArrayQueue queue = new ArrayQueue(queueSize);
queue.enQueue('A');
queue.printQueue();
queue.enQueue('B');
queue.printQueue();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deleted Item : " + deletedItem);
}
queue.printQueue();
}
} |
- 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현.
- "배열의 크기 = 큐의 크기" → 즉, 큐에 저장할 수 있는 최대 원소의 갯수.
- 원형큐는 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주하는 것이다.
- 원형 큐에서는 초기 공백 상태일 때 front와 rear 값이 0이되고,
- 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둔다.
★ 선형큐의 문제를 해결하기 위해 원형큐를 사용(Circular Queue)
선형큐는 포화상태를 확인하기 위해 rear의 위치가 마지막인지를 검사하기때문에 삽입 연산을 수행하면 배열의 앞자리가 비었음에도 포화상태로 인식하고 삽입연산을 수행하지 않는다.
만일 다시 큐의 빈자리를 사용하려면 저장되어 있는 원소를 배열의 앞부분으로 이동시켜서 위치를 조정해주어야 한다. 하지만 이동 작업 연산은 오버헤드를 수반하여 큐의 효율을 떨어뜨린다.
|
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
81
82
83
84
85 |
package Queue;
public class CircularQueue implements Queue{
private int front;
private int rear;
private int queueSize;
private char ItemArray[];
public CircularQueue(int queueSize) {
this.front = 0;
this.rear = 0;
this.queueSize = queueSize;
ItemArray = new char[queueSize];
}
//큐가 비어있는지 확인
@Override
public boolean isEmpty() {
return (front==rear);
}
//큐가 가득차 있는지 확인
public boolean isFull() {
return ((rear+1)%this.queueSize==front);
}
//큐의 삽입 연산
@Override
public void enQueue(char item) {
if(isFull()){
System.out.println("큐가 포화 상태");
}else{
rear = (rear+1)%(queueSize);
ItemArray[rear] = item;
}
}
//큐의 삭제 후 반환 연산
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("큐가 공백 상태");
return 0;
}else{
front = (front+1)%queueSize;
return ItemArray[front];
}
}
//큐의 삭제 연산
@Override
public void delete() {
if(isEmpty()){
System.out.println("삭제할 큐가 없음");
}else{
front = (front+1)%queueSize;
}
}
//큐의 현재 front값 출력
@Override
public char peek() {
if(isEmpty()){
System.out.println("큐가 비어있음");
return 0;
}else{
return ItemArray[(front+1)%queueSize];
}
}
//전체 큐값 출력
public void print(){
if(isEmpty()){
System.out.println("큐가 비어있음");
}else{
int f = front;
while(f!=rear){
f = (f+1)%queueSize;
System.out.print(ItemArray[f] + " ");
}
System.out.println();
}
}
} |
CircularTest.java
|
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 |
package Queue;
public class CircularTest {
public static void main(String[] args) {
int queueSize = 4;
char deletedItem;
CircularQueue queue = new CircularQueue(queueSize);
queue.enQueue('A');
queue.print();
queue.enQueue('B');
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deleteItem : " + deletedItem);
}
queue.print();
queue.enQueue('C');
queue.print();
queue.enQueue('D');
queue.print();
queue.enQueue('F');
queue.print();
deletedItem = queue.deQueue();
if(deletedItem!=0){
System.out.println("deleteItem : " + deletedItem);
}
queue.print();
queue.enQueue('F');
queue.print();
}
} |
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 덱 (Deque) - 연결 자료구조 방식 구현 (0) | 2015.11.04 |
|---|---|
| [자료구조/java] 큐 (Queue) - 연결큐 연결 자료구조 방식 구현 (0) | 2015.11.04 |
| [자료구조/java] 수식의 표기법 - Stack 사용 (1) | 2015.11.02 |
| [자료구조/java] 스택의 응용 - 수식의 괄호 검사 (java) (0) | 2015.10.31 |
| [자료구조/java] 스택의 응용 - 역순 문자열 만들기 (0) | 2015.10.31 |
