배열(Array)과 연결리스트(LinkedList)를 잘 이해했으면 큐(Queue)를 이해하고 구현하는데 어렵지 않다.
위키백과에 보면 큐 자료구조에 대해 다음과 같이 설명하고 있다.
큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
나중에 집어 넣은 데이터가 먼저 나오는(LIFO) 스택과는 반대되는 개념이다.
너무 정확하게 설명해서 더 이상 설명할 것이 없다. 스택과 다른점은 먼저 들어간 놈이 먼저 나온다는 것이다.
일상적으로 이런 사례를 많이 접할 수 있는데 마트에서 계산을 하려고 줄을 서있을것을 생각해보자. 또는 돈을 인출하기위해 ATM에 줄서있는 경우나도 마찬가지이다. 먼저 계산대에 들어온사람 부터 계산하고 다음 사람을 차례차례 계산하고 ATM에서도 먼저 줄 선사람이 먼저 돈을 인출하고 나간다.
이는 일상적인 생활에서지만 프로그래밍적으로는 어떤 경우가 있을까 ?
전략 시뮬레이션 게임인 스타그래프트에서는 처음 적이 어디에 있는지 정찰하는게 매우 중요한데 shift 키 + ? 와 함께 정찰 할 좌표를 예약하여 이동시킬수 있다.
위 그림처럼 예약해놓으면 SCV는 1번 -> 2번 -> 3번 -> 4번 순서대로 이동하게 된다.
1번이 가장 먼저 First In 되었으니 First Out 되서 예약된 행동을 하는 이 구조는 큐와 정확히 일치한다.
이 외에도 큐는 메세지 큐(Message Queue)나 프린터 큐(Printer Queue)등에도 사용된다.
구현은 보통 배열이나 연결리스트로 쉽게 구현 할 수 있고 자바에서 이런 큐 구조 구현체가 있는데 바로 Queue<> 클래스이고 C++ 에서는 stl::queue 가 있다.
|
1
2
3
4
5
6
7
8
9
|
연결리스트가 아닌 배열로 구현 하기위해서는 순환배열 (circular array) ( 책에 따라 원형/환형 배열이라고 부르기도 함_
의 개념을 알고 넘어야가 하는데 원형배열이란 선형배열을 마치 원처럼 구성되어 있는것 처럼 구현하는 것이다.
이 circular array 개념은 이 후에 설명할 덱(deque)에서도 중요한 것 이니 잘 익혀두어야 한다
일단 큐를 배열로 구현하는데 왜 순환배열이 왜 필요한지 부터 설명하겠다.
우선 선형배열을 기준으로 큐를 규현한다고 생각해보자
16개의 큐데이터를 넣을수있는 배열을 선언한다
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
배열에 데이터 5 개를 추가(push)한다 { "a", "b", "c", "d" , "e"} . 그럼 아래 처럼 되어 있을 것이다.
[0="a"] [1="b"] [2="c"] [3="d"] [4="e"] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
큐는 FIFO 구조이니 이제 데이터를 빼기(pop)위해 배열의 맨 앞에서부터 제거해야 한다.
0번 인덱스의 ([0="a"] ) 자료를 뺀다음에 나머지 데이터들을 어떻게 배치해야할지 2가지 방법이 있다.
첫째는 [0="a"] 이후의 데이터들을 앞으로 한칸씩 재 배치하는 것이다.
a <- 0번에서 나오고 "b" 부터 "e" 까지의 원소들을 앞으로 한칸씩 재 배치 하면 아래처럼된다.
[0="b"] [1="c"] [2="d"] [3="e"] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
문제는 이렇게 하면 매번 위치를 갱신해야하는 cost 가 들어가게된다.
|
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
|
public class Main {
public static void main(String[] args) {
LinearArrayQueue<Character> queue = new LinearArrayQueue();
queue.push('a');
queue.push('b');
queue.push('c');
}
private static class LinearArrayQueue<E> {
Object []queue ;
int tail;
public LinearArrayQueue() {
queue = new Object[16];
tail = 0;
}
public void push(E e) {
queue[(++tail - 1)] = e;
}
public E pop() {
// queue is empty
if(tail == 0) {
return null;
}
// 배열 맨 앞에것을 빼고 값을 null 로한다.
E e = (E)queue[0];
queue[0] = null;
--tail;
// 0번째 이 후의 데이터들을 앞으로 한 칸씩 재 배치.
for(int i = 0 ; i < tail ; i++) {
queue[i] = queue[i+1];
}
return e;
}
}
}
Colored by Color Scripter
|
두번째는 위치를 배치하지 말고 push하고 pop 할 index 를 미리 계산해 두는 것이다.
push 할 곳을 tail 로 관리하고 pop할 곳을 head로 관리한다.
[0="a"] [1="b"] [2="c"] [3="d"] [4="e"] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
위 상태라면 현재 tail = 4가 되고 head = -1 이 된다.
push 된다면 tail+1 하여 5번째 인덱스에 값을 넣어주고 pop 한다면 head+1 번째를 빼고 값을 null 로 설정해준다.
|
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
|
public class Main {
public static void main(String[] args) {
LinearArrayQueue<Character> queue = new LinearArrayQueue();
queue.push('a');
queue.push('b');
queue.push('c');
// head = 2, tail = 2
}
private static class LinearArrayQueue<E> {
private Object []queue ;
private int tail;
private int head;
public LinearArrayQueue() {
queue = new Object[16];
head = tail = -1;
}
public void push(E e) {
queue[++tail] = e;
}
public E pop() {
// tail 과 head가 값이 같다면 empty 상태이다.
if(tail == head) {
return null;
}
// 배열 맨 앞에것을 빼고 값을 null 로한다.
// head 가 queue.length 의 길이를 초과 하면 오류가 발생
E e = (E)queue[++head];
queue[head] = null;
return e;
}
public int head() { return head ;}
public int tail() { return tail ; }
}
}
Colored by Color Scripter
|
이 방법은 첫번째 처럼 위치를 재배치해야 하는 cost 는 없지만 심각한 오류가 발생한다.
첫번째 것은 push() 와 pop()을 쌍으로 호출해도 문제가 없지만 두번째 것은 push() 와 pop() 호출 할 때 마다 head, tail 이 계속 증가하기 때문에 head 가 queue.length 의 길이를 초과 하면 오류가 발생한다. 즉 16번밖에 push() / pop() 할수 밖에 없는 구조이다.
뭐 정말 16번 이하로 큐에 데이터가 들어간다면 걱정할 필요 없지만 이건 확장성이 매우 떨어지는 구조일 수 밖에 없다.
순환배열은 이런 단점을 극복하기 위한 알고리즘이라고 보는게 맞다.
배열을 선형적으로 생각하지 말고 circle 로 간주하여 계속 순환되게 하는 것이다.
|
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
|
public class Main {
public static void main(String[] args) {
CircularArrayQueue<Character> queue = new CircularArrayQueue();
}
private static class CircularArrayQueue<E> {
private Object []queue ;
private int tail;
private int head;
public CircularArrayQueue() {
queue = new Object[4];
head = tail = -1;
}
public void push(E e) {
tail = (tail+1)%queue.length;
queue[tail] = e;
}
public E pop() {
// tail 과 head가 값이 같다면 empty 상태이다.
if(tail == head) {
return null;
}
// 배열 맨 앞에것을 빼고 값을 null 로한다.
head = (head+1)%queue.length;
E e = (E)queue[head];
queue[head] = null;
return e;
}
public int head() { return head ;}
public int tail() { return tail ; }
}
}
Colored by Color Scripter
|
CircularArrayQueue 에서 중요한 포인트는 push() 와 pop() 할 때 (head or tail +1) % queue.length 이 부분이다.
현재 위치를 큐의 길이로 모듈러 연산을 하고 이는데 모듈러 연산을 하게되면 head or tail이 +1씩 계속 증가하다가 queue 사이즈랑 동일해지면 다시 0으로 회귀(순환) 하게 된다
코드에서는 테스트를 쉽게하기위해 queue 사이즈를 4로 했는데 이렇게되면 아래처럼 4번을 주기로 계속 인덱스가 반복된다.
push 할 때 마다 tail 값의 변화 : 0 -> 1 -> 2 -> 3 -> 0 -> 1 -> 2 -> 3 -> 0 .. 반복
따라서 큐에서 pop 될 때 나머지 데이터 위치를 한칸씩 앞으로 reposition 할 필요도 없고, push 나 pop을 할 수 있는 횟수에 제약이 생기지도 않는다.
마지막으로 큐의 변형으로 우선순위 큐(Priority Queue) 라는 것이 있는데 이건 Queue와 다르게 큐에 들어간 엘리먼트들은 모두 우선순위있고 우선순위가 가장 높은 높 부터 처리되는 자료구조이다.
'자료구조(Data Structure)' 카테고리의 다른 글
| 이진트리(Binary Tree) (0) | 2019.06.18 |
|---|---|
| 우선순위큐(Priority Queue) (0) | 2019.06.18 |
| 힙(Heap) (0) | 2019.06.18 |
| 트리(Tree) (0) | 2019.06.18 |
| 스택(Stack) (0) | 2019.06.18 |
