2019. 5. 27. 12:05ㆍ컴퓨터공학기초 및 이론/자료구조&알고리즘
큐 형태의 자료구조는 데이터를 쌓아두는 자료구조로, 선입선출(FIFO)인 점이 특징이다. 주로 일시적인 자료의 저장에 많이 사용된다.
큐의 경우 가장 먼저 들어간 데이터를 먼저 꺼내고, 나중에 들어간 데이터를 나중에 꺼내게 되는데 이를 배열로 만들게 될 경우 하나의 데이터를 꺼낼 때 마다 모든 데이터의 위치를 이동해야하는 문제가 있다. 따라서 보통 큐를 만들 때는 Linked list를 이용하거나, ring buffer 형태를 많이 사용한다.
큐에 데이터를 넣는 작업은 인큐(enqueue), 꺼내는 작업은 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽은 프론트(front)라고 하고 데이터를 넣는 쪽을 (rear)라고 한다.
배열로 큐를 생성할 경우, 인큐의 복잡도는 O(1)이 되지만 디큐의 복잡도는O(n)이 된다. 데이터를 꺼낼때마다 이후의 요소를 모두 앞으로 옮겨야 하기 때문이다. 따라서 이러한 문제 때문에 큐를 만들 때에는 링 버퍼 형태의 배열이나 링크드 리스트를 쓰는 것이다.
링 버퍼로 큐를 만드는 것은, 배열을 동그랗게 링 형태라고 상상하는 것이다. 이 경우, 첫 요소의 인덱스를 front라는 변수에 넣고, 맨 끝 요소의 하나 뒤의 인덱스를 rear라는 변수에 넣는다. 그리고 다음 요소를 인큐할 때는 rear에, 데이터를 꺼낼 때는 front의 위치에서 꺼내는 것이다. 즉, 인큐와 디큐가 발생할 때마다 front와 rear의 인덱스를 업데이트 해 준다면, 이 큐는 기존 배열의 큐 상태처럼 데이터를 이동할 필요가 없고, 따라서 복잡도는 O(1)이 된다. O(n)보다 훨씬 더 효과적인 셈이다.
/*출처:자료구조와 함께 배우는 알고리즘입문 자바편 */
public class IntQueue {
private int max; // 큐의 용량
private int front; // 첫 번째 요소 커서
private int rear; // 마지막 요소 커서
private int num; // 현재 데이터 수
private int[] que; // 큐 본체
// 실행 시 예외：큐가 비어 있음
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() { }
}
// 실행 시 예외：큐가 가득 참
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() { }
}
// 생성자
public IntQueue(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max]; // 큐 본체용 배열을 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// 큐에 데이터를 인큐
public int enque(int x) throws OverflowIntQueueException {
if (num >= max)
throw new OverflowIntQueueException(); // 큐가 가득 참
que[rear++] = x;
num++;
if (rear == max)
rear = 0;
return x;
}
// 큐에서 데이터를 디큐
public int deque() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException(); // 큐가 비어 있음
int x = que[front++];
num--;
if (front == max)
front = 0;
return x;
}
// 큐에서 데이터를 피크 (프런트 데이터를 들여다봄)
public int peek() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException(); // 큐가 비어 있음
return que[front];
}
// 큐에서 x를 검색하여 인덱스(찾지 못하면 –1)를 반환
public int indexOf(int x) {
for (int i = 0; i < num; i++) {
int idx = (i + front) % max;
if (que[idx] == x) // 검색 성공
return idx;
}
return -1; // 검색 실패
}
// 큐를 비움
public void clear() {
num = front = rear = 0;
}
// 큐의 용량을 반환
public int capacity() {
return max;
}
// 큐에 쌓여 있는 데이터 수를 반환
public int size() {
return num;
}
// 큐가 비어 있나요?
public boolean isEmpty() {
return num <= 0;
}
// 큐가 가득 찼나요?
public boolean isFull() {
return num >= max;
}
// 큐 안의 모든 데이터를 프런트 → 리어 순으로 출력
public void dump() {
if (num <= 0)
System.out.println("큐가 비어 있습니다.");
else {
for (int i = 0; i < num; i++)
System.out.print(que[(i + front) % max] + " ");
System.out.println();
}
}
}
위에서 만든 링 버퍼 큐의 테스트 코드는 다음과 같다
import java.util.Scanner;
// int형 큐의 사용 예
//알고리즘 자료구조 입문 자바편 출처
class IntQueueTester {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
IntQueue s = new IntQueue(64); // 최대 64개를 인큐할 수 있는 큐
while (true) {
System.out.println("현재 데이터 수：" + s.size() + " / "
+ s.capacity());
System.out.print("(1)인큐 (2)디큐 (3)피크 " +
"(4)덤프 (0)종료：");
int menu = stdIn.nextInt();
if (menu == 0) break;
int x;
switch (menu) {
case 1: // 인큐
System.out.print("데이터：");
x = stdIn.nextInt();
try {
s.enque(x);
} catch (IntQueue.OverflowIntQueueException e) {
System.out.println("큐가 가득 찼습니다.");
}
break;
case 2: // 디큐
try {
x = s.deque();
System.out.println("디큐한 데이터는 " + x + "입니다.");
} catch (IntQueue.EmptyIntQueueException e) {
System.out.println("큐가 비어 있습니다.");
}
break;
case 3: // 피크
try {
x = s.peek();
System.out.println("피크한 데이터는 " + x + "입니다.");
} catch (IntQueue.EmptyIntQueueException e) {
System.out.println("큐가 비어 있습니다.");
}
break;
case 4: // 덤프
s.dump();
break;
}
}
}
}이 코드는 최대 용량이 64인 큐를 생성하고 인큐, 디큐, 피크, 큐의 데이터 출력을 대화식으로 실행한다.
링 버퍼형태의 큐가 일반 배열형태의 큐보다 복잡도가 낮다는 점은 알 수 있지만, 이렇게만 봐서는 어떤 용도로 사용하는가에 대해 의문이 생길 수 있다. 링 버퍼 큐는 '오래된 데이터를 버리는' 용도로 사용할 때에 효과적인데, 예를 들어 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 식이다.
아래 코드의 주석을 보면 이해할 수 있을 것이다.
import java.util.Scanner;
public class LastNElements {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
final int N = 10;
int[] a = new int[N];
int cnt = 0;
int retry;
System.out.println("정수를 입력하세요.");
do{
System.out.printf("%d번째 정수:", cnt + 1);
a[cnt++ % N] = stdIn.nextInt();
System.out.print("계속 할까요? (1.예/0.아니오) :");
retry = stdIn.nextInt();
} while (retry == 1);
/*
*
* 입력한 값을 저장할 때, 상수로 선언한 N 크기의 큐를 cnt가 넘어가면
* 맨 처음에 넣은 것들을 지워줘야 한다. N보다 작은 경우에는 0 인덱스부터 cnt-1 인덱스까지를
* 출력하면 되지만, N을 넘어설 경우에는 N을 초과한 크기만큼의 인덱스부터 시작해야한다.
* 따라서 입력한 값을 저장하는 위치의 인덱스를 cnt++%N 으로 할 경우, 인덱스는 N을 cnt로 나눈 나머지값이 되며
* 10이 넘어갈 경우 다시 0번 인덱스부터 값을 저장하게 된다.이렇게 하면 10개의 범위를 넘어서는 데이터에 대해
* 링 버퍼의 형태로 먼저 들어온 데이터가 사라지고 최신 10개의 데이터만 유지된다는 것을 알 수 있다.
* */
int i = cnt - N;
if (i < 0) i = 0;
for (; i <cnt; i++)
System.out.printf("%2d번째의 정수 = %d\n", i + 1, a[i % N]);
}
}
큐라는 형태의 자료구조를 실제로 어떻게 활용할 수 있을지는 잘 모르겠지만, 큐라는 자료구조의 형태나 특징에 대해서 이정도면 기초적인 정리가 된 것 같다.
다음으로 링크드리스트(Linked List)를 알아보겠다. 링크드리스트는 큐를 만들때 일반적으로 사용하는 함수라고 볼 수 있다. 특히 배열에 비해 데이터를 특정 위치에 추가하거나 지우는 것에 효과적이다. 인덱스 연산의 속도는 낮은 대신 데이터의 추가, 삭제가 효과적이라는 것이 배열(arrayList)과의 차이라고 볼 수 있다.
출처 : 위키미디아
위 세 가지 그림은 링크드리스트의 형태를 보여준다. 데이터 하나당 다음 데이터의 위치를 가리키는 노드를 붙여 다음 데이터의 위치와 현재 데이터의 노드가 연결된 상태로 여겨지게 하는 것이 링크드 리스트의 특징이다. 따라서 중간에 값을 빼거나 넣을때에도 위치정보만 수정되면 된다는 점에서 효율적이라는 것을 알 수 있다. 특히 데이터가 방대할 경우 arrayList로는 도저히 엄두가 안나는 것도 링크드리스트 형태라면 훨씬 수월하게 해결 할 수 있다.
아래는 링크드리스트에 대한 예제 코드이다
import java.util.LinkedList;
public class LinkedListEX {
public static void main(String[] args) {
LinkedList firstList = new LinkedList();
LinkedList secondList = new LinkedList();
String[] testVal = {"가","나","다","라","마"};
//링크드 리스트를 출력한다
for(int i = 0; i<testVal.length; i++){
firstList.add(testVal[i]);
System.out.println(firstList);
}
System.out.println("======================");
//링크드리스트의 각종 메소드를 확인한다
for(int k=0; k<testVal.length; k++){
//기존 리스트에 다시 값을 하나씩 더한다.
firstList.add(testVal[k]);
System.out.println(firstList);
//poll 메소드는 꺼낸 값을 리스트에서 뺀다
firstList.poll();
//peek 메소드는 링크드리스트의 head요소를 사용한다(맨 앞의 요소). 맨 앞의 요소를 보여주지만 리스트에서 빼지는 않는다.
System.out.println(firstList.peek());
}
System.out.println("======================");
System.out.println(firstList);
//clone 메소드를 통해 링크드리스트를 복제한다. object 형으로 복제하기 때문에 링크드리스트로 캐스트를 해준다.
secondList = (LinkedList) firstList.clone();
System.out.println(secondList);
//remove는 인덱스 위치에 있는 값을 제거한다
secondList.remove(1);
System.out.println(secondList);
//맨 마지막에 데이터를 추가한다
secondList.addLast("가");
System.out.println(secondList);
}
}
'컴퓨터공학기초 및 이론 > 자료구조&알고리즘' 카테고리의 다른 글
| 소수 찾기 메모 (0) | 2020.06.28 |
|---|---|
| 스택(stack) (0) | 2019.05.27 |
| 복잡도와 점근표기법(빅오표기법) (0) | 2019.05.21 |
| 이진 탐색 (binary-search) (0) | 2019.05.21 |
| 보초법 sentinel method (0) | 2019.05.20 |