-
자바로 배우는 큐 (Queue)Software/Data Structure : 자료구조 2019. 10. 31. 01:49반응형
개념
기본 자료 구조의 하나로 선입선출 / FIFO (First In First Out) 형태로 데이터를 추가하고 반환한다. Stack 의 후입선출 (LIFO)와 반대.
인터페이스
enqueue(value): 데이터를 입력/추가
dequeue(): 가장 처음에 입력된 혹은 스택에 가장 아래에 위치하고 있는 항목을 반환
구현
큐 또한 스택과 같이 배열과 연결리스트를 통해 구현이 가능하지만 이번에는 배열을 통한 구현을 해보았다. 아마도 개념 이해에는 더 쉬울 거라 생각된다.
큐는 선입선출(FIFO)의 형태를 가지므로 enqueue()가 호출되었을 때 순차적으로 배열에 저장을 하고 front index를 하나씩 증가시켜준다. 그리고 dequeue()가 호출되었을 때는 rear index 위치에 있는 queue 배열의 데이터를 반환한다. rear index는 0부터 시작해서 dequeue가 호출될 때마다 하나씩 증가한다. 구현 및 테스트 코드는 아래와 같다.
class Queue { private static final int MAX_N = 100; private int mFront; private int mRear; private int mQueue[] = new int[MAX_N]; Queue () { mFront = 0; mRear = 0; } boolean isEmpty() { return (mFront == mRear); } boolean isFull() { return (mFront + 1) % MAX_N == mRear; } boolean enqueue(int value) { if (isFull()) { System.out.print("queue is full!"); return false; } mQueue[mFront] = value; mFront++; if (mFront == MAX_N) { mFront = 0; } return true; } Integer dequeue() { if (isEmpty()) { System.out.print("queue is empty!"); return null; } Integer value = new Integer(mQueue[mRear]); mRear++; if (mRear >= MAX_N) { mRear = 0; } return value; } }
동작 확인
private static void testQueue() { Queue queue = new Queue(); for (int i = 0; i < 10; i++) { System.out.print("enqueue value: " + i + "\n"); queue.enqueue(i); } System.out.print("\n"); while(!queue.isEmpty()) { System.out.print("dequeue value: " + queue.dequeue() + "\n"); } }
enqueue value: 0 enqueue value: 1 enqueue value: 2 enqueue value: 3 enqueue value: 4 enqueue value: 5 enqueue value: 6 enqueue value: 7 enqueue value: 8 enqueue value: 9
dequeue value: 0 dequeue value: 1 dequeue value: 2 dequeue value: 3 dequeue value: 4 dequeue value: 5 dequeue value: 6 dequeue value: 7 dequeue value: 8 dequeue value: 9
반응형'Software > Data Structure : 자료구조' 카테고리의 다른 글
자바로 배우는 스택 (Stack) (0) 2019.10.30 댓글