[자료구조] 큐(Queue)와 Java로 구현

큐(Queue)

FIFO(First In First Out) 특성을 가진 자료구조

데이터가 들어오는 위치는 가장 뒤로 후단(Rear or Back)이라 하고,

데이터가 나가는 위치는 가장 앞인 전단(Front)이다

스택에서는 삽입, 삭제 모두 top을 통해서 이루어지는데,

큐에서는 front에서 삭제, rear에서 삽입을 담당한다

 

큐의 추상자료형(Abstract Data Type; ADT)

- 입력 : 엔큐(Enqueue) 

- 출력 : 디큐(Dequeue) 

※ 간혹 스택과 동일하게 Push,Pop을 쓰기도 하고, Push,Pull을 사용하기도 한다

 

큐의 종류

1. 선형 큐

	- 1차원 배열을 정의한다 - 삽입, 삭제를 위한 변수인 front와 rear을 만든다 - front와 rear의 초기값은 -1이다
	- 데이터를 추가하기 전에 rear의 값을 1 증가시킨다
	- rear의 위치에 데이터를 넣는다
	- 데이터를 삭제하기 위해 front의 값을 1 증가시킨다
	- front의 위치에 있는 데이터를 삭제시킨다

- 간단하게 큐를 1차원의 배열로 놓고 이용하는 방법

- 배열을 이용한 큐이기 때문에 Enqueue와 Dequeue를 할 때마다 데이터가 앞으로 밀려나는 문제가 생긴다

-즉 front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하기 때문에, 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 하는 문제가 있다

 

2. 원형 큐

	- 선형 큐의 문제를 해결하는 방법 - front와 rear의 값이 배열의 끝에 도달하면 다음 값은 처음 값인 0으로 돌아오게 된다 - 실제 배열이 원형으로 변화되는 것이 아니고, 개념 상 원형으로 배열의 인덱스 값을 변경해주는 방법이다 - 선형 큐와 다르게 front와 rear의 초기값이 0이다
	- 데이터를 추가하기 위해 rear의 값을 1 증가시킨다
	- rear의 위치에 데이터를 삽입한다
	- 데이터를 삭제하기 위해 front의 값을 1 증가시킨다
	- front의 위치에 있는 데이터를 삭제한다 - front와 rear의 값이 같은 경우, 원형 큐가 비어있음을 나타낸다

 - 원형 큐에서는 포화상태와 공백 상태를 구별하기 위해서 항상 하나의 자리는 비워둔다

 

Java로 구현(배열 이용)

public class queueRealization {
	public static void main(String[] args) {
		Queue queue = new Queue();
		System.out.println("----push----");
		for(int i=0; i<100; i++) {
			int num=i;
			queue.push(num);
			System.out.println(num);
		}
		
		System.out.println("----pop----");
		for(int i=0; i<100; i++) {
			queue.pop();
		}

		System.out.println("----peek----");
		System.out.println(queue.peek());
	}
}

class Queue{
	int MAX = 100;
	int front = 0;
	int rear = 0;
	int[] queue;
	
	public Queue() {
		queue = new int[MAX];
	}
	
	void push(int value) {
		if(is_full())
			System.out.println("Queue is full!");
		else {
			if(++rear==MAX) 
				rear = 0;
			queue[rear] = value;
		}
	}
	
	void pop() {
		if(is_empty()) {
			System.out.println("Queue is Empty");
		}
		if(++front==MAX)
			front=0;
		queue[front]=0;
	}
	
	boolean is_full() {	//포화상태 체크
		if((front-rear)==1 || front==0&&rear==(MAX-1))
			return true;
		return false;
	}
	
	boolean is_empty() {
		if(front==rear)
			return true;
		return false;
	}
	
	int peek() {
		return queue[rear];
	}
	
}