큐(Queue)란

큐(Queue)

이전 포스팅인 스택에 이어서 큐에 대해 알아보고 배열과 링크드리스트를 이용해 구현해보려고 합니다. 

 

 

큐(Queue)란? 

 

큐는 줄(Line)이라는 의미를 가지고 있습니다. 지난 번 스택은 선입후출(First In Last Out)이라고 했었죠?

반대로 큐는 선입선출(First In Fitst Out) 형태의 자료구조입니다. 줄로 설명하자면 가장 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 떠올려볼 수 있습니다.

 

 

큐에서 가장 오래전에 입력된 데이터는 front (head) 라고 하며 가장 최근에 입력된 데이터는 rear (tail) 라고 합니다. 큐는 선입후출의 구조이기 때문에 데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어집니다.

 

 

 

큐의 메소드

 

- add(e)와 offer(e)는 큐에 데이터를 추가합니다.

(add와 offer은 모두 데이터를 추가하지만, 이미 큐가 꽉 찬 경우 add는 예외를 발생시키고 offer는 추가 실패를 의미하는 false를 리턴한다는 차이점이 있습니다)

- poll()은 front가 가리키는 값을 삭제 후 return 합니다. 

- peek()은 front가 가리키는 값을 읽는 작업입니다. 데이터를 제거하지 않고 읽는 작업만 수행하므로 front 값을 변경시키지 않습니다.

 

 

 

큐의 구현

 

다음 코드는 큐를 배열을 이용해 자바로 구현한 것입니다.

public class ArrayQueue {
	private int front;
	private int rear;
	private int maxSize;
	private Object[] Queue;
	
	
	//maxSize로 스택을 생성
	public ArrayQueue(int maxSize) {
		Queue = new Object[maxSize];
		this.front = 0;
		this.rear = -1;
		this.maxSize = maxSize;
	}
	
	public boolean isEmpty() {
		return (front == rear+1);
	}
	
	public boolean isFull() {
		return (maxSize == rear+1);
	}
	
	public void add(Object item) {
		if(isFull()) throw new ArrayIndexOutOfBoundsException();
		Queue[++rear]=item;
	}
	
	public Object peek() {
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException();
		return Queue[front];
	}
	
	public Object poll() {
		Object data = peek();
		front++;
		return data;
	}
	
	public static void main(String[] args) {
	
		ArrayQueue test = new ArrayQueue(5);	
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("큐가 비어있지 않습니다.");
		}
		
		test.add(1);
		test.add(2);
		test.add(3);
		
		
		System.out.println("큐의 front에 들어있는 값은 : " + test.peek());
		test.poll();
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("큐가 비어있지 않습니다.");
		}
		
		System.out.println("큐의 front에 들어있는 값은 : " + test.peek());
		
	}

}

 

 

다음은 큐를 링크드리스트를 이용해 자바로 구현한 것입니다.

(add 메소드에서 큐가 비어있을 때를 따로 처리해주어야 합니다.)

 

public class LinkedListQueue {
	
	private QueueNode front;
	private QueueNode rear;

	class QueueNode{
		private Object data;
		QueueNode next;
		
		public QueueNode(Object input) {
			this.data = input;
			this.next = null;
		}
		
	}
	
	 public LinkedListQueue(){
	        this.front = null;
	        this.rear = null;
	    }

	public void add(Object data) {
		QueueNode newQueueNode = new QueueNode(data);
		newQueueNode.next = null;
		
		if(isEmpty()) {
			front = newQueueNode;
			rear = newQueueNode;
		}
		else {
			rear.next = newQueueNode;
			rear = newQueueNode;

		}
	}
	
	public Object poll() {
		Object data = peek();
		front = front.next;
		
		return data;
	}
	
	public Object peek() {
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException();
		return front.data;
	}
	
	public boolean isEmpty() {
		return (front==null);
	}
	
	public static void main(String[] args) {
		

		LinkedListQueue test = new LinkedListQueue();	
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("큐가 비어있지 않습니다.");
		}
		
		test.add(1);
		test.add(2);
		test.add(3);
		
		System.out.println("큐의 맨 앞에 들어있는 값은 : " + test.peek());
		test.poll();
		
		if(test.isEmpty()) {
			System.out.println("아직 비어있습니다.");
		}
		else {
			System.out.println("스택이 비어있지 않습니다.");
		}
		
		System.out.println("스택의 맨 위에 들어있는 값은 : " + test.peek());
		
	}
}

 

 

 

 

자바에서의 큐의 활용

 

이렇게 구현해본 큐는 자바에서 어떻게 활용할 수 있을까요?

자바에서 큐는 인터페이스이므로 객체 생성이 불가능합니다. 따라서 링크드리스트를 형변환하여 조작해야 합니다.

 

import java.util.LinkedList;

import java.util.Queue;

 

queue<Integer> queue = new LinkedList<>();

 

이런 식으로 말이죠! 그럼 자바에서 큐 활용 예제까지 보고 포스팅을 마무리하도록 하겠습니다. :)

 

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


public class QueueTest {
	public static void main(String[] args) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(4);
		queue.add(5);
		queue.add(6);
		

		System.out.println(queue.peek()); //큐의 front가 가리키는 값을 반환한다.
		System.out.println(queue.poll()); //큐의 front가 가리키는 값을 반환하고 삭제한다.
		
		System.out.println(queue.isEmpty()); // false
		
		System.out.println(queue.peek()); //큐의 front가 가리키는 값을 반환한다.
		
		System.out.println(queue);	
		
	}
}