[자료 구조] 6. 큐 구현하기

[자료구조] 6. 큐 구현하기

1. 큐(Queue)란?

2. 배열을 사용해 큐 구현하기

3. 배열을 사용해 큐를 순환 구조로 구현하기

---

 

1. 큐(Queue)란?

(1) 큐의 개념

큐(Queue)는 데이터를 저장하는 선형 자료구조로, 차례를 기다리는 줄이라는 의미를 지니고 있다. 먼저 들어온 자료부터 순서대로 처리하는 방식을 큐(Queue)라고 말한다.

 

큐는 한 쪽 끝에서는 자료의 삽입 연산, 반대쪽 끝에서는 삭제만 가능한 구조이다.

즉, 선입선출(FIFO: First In First Out)의 특징을 지닌다.

 

(2) 큐의 특징

-맨 앞(front)에서 자료를 꺼내거나, 삭제하고, 맨 뒤(rear)에서 자료를 추가한다.

-선입선출(FIFO) 구조

-일상 생활에서 일렬로 줄 서 있는 모양과 유사하다.

-순차적으로 입력된 자료를 순서대로 처리하는데에 많이 사용되는 자료구조.

-콜센터에 들어온 문의전화, 메세지 등에 큐가 사용된다.

 

*우선 순위 큐(Priority Queue): 원소들을 우선순위에 따라 저장한다. 큐의 FIFO 구조를 따라가지 않는 유일한 큐이다.

---

2. 배열을 사용해 큐 구현하기

 

*아래의 방식은 큐의 끝에 도달했을 때, 자동으로 시작 위치로 돌아가지 않으므로 일반적인 큐의 동작 방식이다.

(순환 방식이 아니다.)

package Structure.ch03;

public class IntArrayQueue {

	private int[] array;
	private int front; // 큐의 시작 점
	private int rear; // 큐의 끝 지점
	private int capacity; // 큐의 용량
	private int size; // 요소의 개수

	public IntArrayQueue(int capacity) {
		this.capacity = capacity;
		array = new int[this.capacity];
		this.front = 0; // 시작점이 0이다
		this.rear = -1; //
		this.size = 0;  
	} // 생성자
	
	// 편의 기능 만들어보기
	public boolean isEmpty() {
		return size == 0; // 비어있다면 true, 아니라면 false
	}
	
	public boolean isFull() {
		return size == capacity; // 가득 찼다면 true, 아니라면 false
	}
	
	// todo 1 - 데이터 넣기 기능 구현
	public void enqueue(int item) {
		if(isFull()) {
			System.out.println("큐 메모리 공간이 가득합니다.");
		} else {
			// rear = -1;
			rear++; // 0 <-- 첫 동작시 
			array[rear] = item; // array[0] = item;
			size++;
		}
	}
	
	// todo 2 - 데이터 꺼내기 기능 구현 
	public int dequeue() {
		int item = -9999;
		if(isEmpty()) {
			System.out.println("큐 메모리 공간이 비어있습니다.");
		} else {
			// 잠시 데이터 꺼내보기
			item = array[front]; // 0번째 요소를 접근
			//100 200 300
			// f - 0 (첫 꺼낼 시)
			for(int i=front; i<rear; i++) { // 0 < 2
				// array[0] = array[1]
				// 200, 200, 300 --> 첫번째 동작 (for)
				// 200, 300, 300 --> 두번째 동작 (for)
				array[i] = array[i+1]; 
			}
			// 200, 300, 0
			// 마지막 요소를 초기화 처리한다.
			array[rear] = 0;
			rear--;
			size--;
		}
		return item;
	}
	
	
	// todo 3 - 데이터 찾기 기능 구현 (peek)
	public int peek() {
		int item;
		if(isEmpty()) {
			System.out.println("큐 메모리 공간에 요소가 없습니다.");
			item=-9999;
			return item;
		} else {
			item=array[front];
			System.out.println("Peak : "+ item);
			return item;
		}
	}

 

---

3. 배열을 사용해 큐를 순환 구조로 구현하기

-나누기 연산(%)을 이용해 순환 구조의 큐를 구현해보자.

 

	// todo 1 - 데이터 넣기 기능 구현
	public void enqueue(int item) {
			// 코드 수정
			// [10] [20] [30]
			// 나머지 연산자를 활용한다.
			// 1 = 1 % 5; 
			// 몫 0, 나머지 1
			// 2 = 2 % 5;
			// 몫 0, 나머지 2
			
			// x =   0  %  3 (임시값 3), rear = 0
			// x =   1  %  3  --> rear = 1
			// x =   2  %  3  --> rear = 2
			// x =   3  %  3  --> rear = 0
			// x =   1  %  3  --> rear = 1
			rear = (rear+1) % capacity;
			array[rear] = item;
			size++;
	}
	
	// todo 2 - 데이터 꺼내기 기능 구현 
	public int dequeue() {
		if(isEmpty()) {
			System.out.println("Queue is empty.");
			return -9999;
		}
		int item = array[front];
		// [10] [20] [30]
		front = (front+1)%capacity;
		return item;
	}
	
	
	// todo 3 - 데이터 찾기 기능 구현 (peek)
	public int peek() {
		int item;
		if(isEmpty()) {
			System.out.println("큐 메모리 공간에 요소가 없습니다.");
			item=-9999;
			return item;
		} else {
			item=array[front];
			return item;
		}
	}
	
	//
	public void printAll() {
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return;
		}
		for(int i=0; i<array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}