[JAVA/자료구조] 큐(Queue)

   큐란?

큐는 먼저 들어온 데이터가 먼저 나가는 구조로, 선입 선출(FIFO:First-Int First-Out)이라고 한다.
큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다.

 

   큐의 구조

- 전단(front): 큐에서 삭제가 일어나는 곳
- 후단(rear): 큐에서 삽입이 일어나는 곳

 

   큐의 연산

- create(): 큐를 생성한다.
- init(): 큐를 초기화한다.
- is_empty(q): 큐가 비어 있는지를 검사한다.
- is_full(q): 큐가 가득 찼는지를 검사한다.
- enqueue(q, e): 큐의 뒤에 요소를 추가한다.
- dequeue(q): 큐의 앞에 있는 요소를 반환한 다음 삭제한다.
- peek(q): 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.

   큐의 구현   

구현 1 배열을 이용한 큐

1. 선형큐

선형큐는 front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 더이상 삽입하지 못한다는 단점이 있다. 따라서 후단에 더 이상 삽입할 공간이 없으면 모든 요소들을 왼쪽으로 이동시켜야 한다. 하지만 매번 이동시키려면 상당한 시간이 걸리고 또한 프로그램 코딩이 복잡해진다.
이는 2번의 원형 큐의 개념을 이용해 이용해 머리와 꼬리가 연결된 형태의 큐를 구현하여 해결한다.

package DataStructure;

import java.util.Scanner;

public class ArrayQueue {
	private int front;
	private int rear;
	private int maxSize;
	private Object[] queueArray;

	// 큐 배열 생성
	public ArrayQueue(int maxSize) {
		this.front = -1;
		this.rear = -1;
		this.maxSize = maxSize;
		this.queueArray = new Object[maxSize];
	}

	// 큐가 비어있는지 체크
	public boolean isEmpty() {
		return (front == rear);
	}

	// 큐가 꽉 찼는지 체크
	public boolean isFull() {
		return (rear == maxSize - 1);
	}

	// 큐 rear에 데이터 등록
	public boolean enqueue(Object item) {
		if (isFull()) { // 스택이 포화상태이면
			for (int i = 0; i < maxSize; i++) {
				System.out.println("| Queue is full |");
				System.out.println("-------");
			}
			return false;
		}
		queueArray[++rear] = item;
		System.out.println("rear: " + rear);
		System.out.println("front: " + front);
		return true;
	}

	// 큐에서 front 조회
	public Object peek() {
		if (isEmpty()) {
			System.out.println("| Queue is empty |");
			return null;
		} else {
			System.out.println("rear: " + rear);
			System.out.println("front: " + front);
			return queueArray[front + 1];
		}
	}

	// 큐에서 front제거
	public Object dequeue() {
		Object item = peek();
		queueArray[++front] = "empty state";
		System.out.println("rear: " + rear);
		System.out.println("front: " + front);
		return item;
	}

	// 큐 출력
	public void printQueue(ArrayQueue queue) {
		if (!isEmpty()) {// 비어있지 않다면
			for (int i = rear; i >= 0; i--) {
				System.out.println("| " + queue.queueArray[i] + " |");
				System.out.println("-------");
			}
		} else {
			System.out.println("| queue is empty |");
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int maxSize = sc.nextInt();

		ArrayQueue arrayQueue = new ArrayQueue(maxSize);

		boolean flag = true;
		while (flag) {
			menu();
			String s = sc.next();

			switch (s) {
			// enqueue()
			case "1":
				System.out.println("enqueue: ");
				String data = sc.next();
				arrayQueue.enqueue(data);
				break;

			// dequeue()
			case "2":
				System.out.println("dequeue: " + arrayQueue.dequeue());
				break;

			// peek()
			case "3":
				System.out.println("peek: " + arrayQueue.peek());
				break;

			// 큐 데이터 출력
			case "4":
				arrayQueue.printQueue(arrayQueue);
				break;

			// 종료
			case "q":
			case "Q":
				System.out.println("종료");
				flag = false;
				break;
			}
		}

	}

	public static void menu() {
		System.out.println("1. enqueue");
		System.out.println("2. dequeue");
		System.out.println("3. peek");
		System.out.println("4. queue");
		System.out.println("q. 종료");
	}
}

 

2. 원형큐

배열을 선형으로 생각하지 않고 원형으로 생각하면 위의 문제를 해결할 수 있다.
즉, front와 rear의 값이 배열의 끝인 MAX_QUEUE_SIZE-1에 도달하면 다음에 증가되는 값은 0이 되도록 한다.

- isEmpty(): front와 rear의 값이 같으면 원형큐가 비어 있는 공백상태이다
- isFull(): 원형큐에서 하나의 자리는 항상 비워두는데 이는 공백상태와 포화상태를 구별하기 위해서이다.
따라서 원형큐에서 front가 rear보다 하나 앞에 있으면 포화상태가 된다. front가 rear보다 하나 앞에 있는 것을 검사하기 위하여, rear의 다음 위치는 (rear+1)를 MAX_QUEUE_SIZE로 나눈 나머지로 구한다.
- enqueue(x): 삽입 전에 먼저 front와 rear를 원형 회전 시켜서 하나 증가 시키고 증가된 위치에 데이터를 삽입해야 한다. front=(front+1)%MAX_QUEUE_SIZE;
- dequeue(): 삭제 전에 먼저 front와 rear를 원형 회전 시켜서 하나 증가시키고 증가된 위치에 데이터를 삭제해야 한다.
rear=(rear+1)%MAX_QUEUE_SIZE;
- init(): 초기화는 공백상태로 만드는 것을 의미하므로 front와 rear를 동일한 값으로 설정한다.
여기서는 모두 0으로 초기화한다.
- size(): 항목의 개수는 rear-front에 전체 항목의 수를 더한 값이된다. 

package DataStructure;

import java.util.Scanner;

public class CircularQueue {
	public int maxSize;
	public int front, rear;
	public Object[] queue;

	// 큐 배열 생성
	public CircularQueue(int maxSize) {
		this.maxSize = maxSize;
		this.front = this.rear = 0;
		queue = new Object[maxSize];
	}

	// 큐 초기화
	public void init() {
		front = rear = 0;
	}

	// 큐가 비어있는지 체크
	public boolean isEmpty() {
		return front == rear;
	}

	// 큐가 가득찼는지 체크
	public boolean isFull() {
		return front == (rear + 1) % maxSize;
	}

	// 큐 안의 요소 개수
	public int size() {
		return (rear - front + maxSize) % maxSize;
	}

	// 큐에서 front 조회
	public Object peek() {
		if (isEmpty()) {
			System.out.println("queue is empty");
			return null;
		} else {
			return queue[(front + 1) % maxSize];
		}
	}

	// 삽입 연산
	public void enqueue(int x) {
		if (isFull()) {
			System.out.println("queue is full");
		}
		rear = (rear + 1) % maxSize;
		System.out.println("회전 후 rear: " + rear);
		queue[rear] = x;

	}

	// 삭제 연산
	public Object dequeue() {
		Object item = peek();
		front = (front + 1) % maxSize;
		return item;
	}

	// 큐 출력
	public void printQueue(CircularQueue circularQueue) {
		System.out.println("reart: " + rear);
		System.out.println("front: " + front);
		int i, maxi = rear;
		if (front >= rear)
			maxi += maxSize;
		for (i = front + 1; i <= maxi; i++) {
			System.out.println("i:" + i);
			System.out.println("maxi:" + maxi);
			System.out.print(circularQueue.queue[i % maxSize] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int maxSize = sc.nextInt();

		CircularQueue circularQueue = new CircularQueue(maxSize);

		boolean flag = true;
		while (flag) {
			menu();

			String s = sc.next();
			switch (s) {
			case "1":
				System.out.println("초기화");
				circularQueue.init();
				break;
			case "2":
				System.out.println("큐의 크기: " + circularQueue.size());
				break;
			case "3":
				System.out.println("peek: " + circularQueue.peek());
				break;
			case "4":
				System.out.println("enqueue: ");
				int x = sc.nextInt();
				circularQueue.enqueue(x);
				break;
			case "5":
				System.out.println("dequeue: " + circularQueue.dequeue());
				break;
			case "6":
				circularQueue.printQueue(circularQueue);
				break;

			// 종료
			case "q":
			case "Q":
				System.out.println("종료");
				flag = false;
				break;
			}
		}
	}

	public static void menu() {
		System.out.println("1. init");
		System.out.println("2. size");
		System.out.println("3. peek");
		System.out.println("4. enqueue");
		System.out.println("5. dequeue");
		System.out.println("6. printQueue");
		System.out.println("q. 종료");
	}
}

배열을 이용하여 구현한 큐는 스택과 같이 크기가 제한된다는 약점이 있다.
따라서 이러한 문제를 해결하기 위해서는 연결리스트를 이용한 큐를 사용해야 한다.

 

구현 2 연결리스트를 이용한 큐

(추가 예정...)  

 

구현 3 자바 Collections 인터페이스 사용

클래스로 구현된 스택과는 달리 자바에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다.
따라서 Queue에서는 Queue로 인스턴스화 하지 않고, Queue인터페이스로 만든 다양한 클래스 중 LinkedList클래스를 사용하여 Queue를 인스턴스화한다.

1) Queue의 선언

import java.util.Queue;
import java.util.LinkedList;

Queue<String> q = new LinkedList<String>();

Queue인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection인터페이스 메소드만을 상속받아 사용한다.

2) Queue의 메소드

public void offer(Element data); //값을 입력받아 순차 보관
public Element poll(); //가장 먼저 보관한 값 꺼내고 반환
public Element peek(); ///가장 먼저 보관한 값 단순 참조, 꺼내지 않음
public boolean empty(); //비어있는지 판별

 

3) 예제 코드

package DataStructure;

import java.util.LinkedList;
import java.util.Queue;

public class QueueInterface {
	public static void main(String[] args) {
		Queue<String> q = new LinkedList<String>();
		q.offer("1");
		q.offer("2");
		System.out.println(q.peek());

		System.out.println(q.poll());
		q.offer("3");
		q.offer("4");
		while (q.isEmpty() == false) {
			System.out.println(q.poll());
		}
	}
}

< 실행 결과 >

 

   Reference

 

선형큐
https://mailmail.tistory.com/33

[자료구조] 선형 큐의 기능 및 구현

원형큐
https://mailmail.tistory.com/41?category=724615

[자료구조] 원형 큐의 기능 및 구현

java의 스택과 큐
http://tcpschool.com/java/java_collectionFramework_stackQueue

코딩교육 티씨피스쿨

java 컬렉션 정리
https://gangnam-americano.tistory.com/41

[JAVA] Java 컬렉션(Collection) 정리