[Java] 큐(Queue) 배열로 구현하기

1.Queue란?

큐

• 먼저 들어온 데이터가 먼저 나간다. 즉, 선입선출(FIFO) 방식이다.
• 맨 앞의 원소에만 접근이 가능하다. 

2. Queue 구현하기

구현할 내용은 아래와 같다.

• enqueue(E x) - 원소 x를 큐의 끝에 추가한다.
• dequeue() - 큐의 가장 앞에 있는 원소를 삭제한다.
• front() - 큐의 가장 앞에 있는 원소를  리턴한다.
• isEmpty() - 큐가 비어있으면 true, 그렇지 않으면 false를 리턴한다.
• dequeueAll() - 큐에 있는 모든 원소를 삭제한다.
• printAll() - 큐의 모든 원소를 순서대로 출력한다.

** 원래 큐에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

 

1) 인터페이스

public interface QueueInterface<E> {

	public void enqueue(E x);
	
	public void dequeue();
	
	public E front();
	
	public boolean isEmpty();
	
	public void dequeueAll();
	
	public void printAll();
	
}

 

2) 클래스

- 필드 영역

private E queue[];
private int front, tail, size;
private static final int DEFAULT_CAPACITY = 64;

• queue[] - ArrayQueue의 원소를 받을 배열 리스트이다.
• front, tail - ArrayQueue의 맨 첫 원소, 마지막 원소를 표시할 포인터이다.
• size -  ArrayQueue의 원소 개수를 저장할 변수이다.
• DEFAULT_CAPACITY - ArrayQueue 생성시 크기를 정해주지 않으면 해당 크기로 생성한다.

- 생성자 영역

	public ArrayQueue() {
		queue = (E[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	public ArrayQueue(int n) {
		queue = (E[]) new Object[n];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

• 입력 값으로 정수를 받으면 해당 정수 크기의 큐를, 그렇지 않으면 DEFAULT_CAPACITY 크기의 큐를 생성한다.

- 메서드 영역

<is Full 메서드 구현>

public boolean isFull() {
		return (size==queue.length);
	}

• 인터페이스의 메서드를 오버라이딩 한 것은 아니다.
• 현재 size 변수(원소의 개수)와 생성시 배정한 queue의 크기가 같으면 true, 아니면 false를 리턴한다.

<enqueue 메서드 구현>

	@Override
	public void enqueue(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			tail = (tail+1)%queue.length;
			queue[tail]=x;
			size++;
		}
	}

• 만약 큐에 빈 공간이 없으면 에러를 출력한다.
• 그렇지 않다면 tail에 1을 더해주고 해당 위치에 입력받은 값을 입력한다.
• queue.length로 나눠주는 이유는 tail 포인터가 큐의 끝까지 도달했을 때 맨 앞 위치로 돌려놓기 위해서이다.
• size 변수를 1 증가시킨다.

<dequeue 메서드 구현>

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		}
		queue[front]=null;
		front=(front+1)%queue.length;
		size--;
	}

• 만약 큐가 비어 있으면 에러를 출력한다.
• 그렇지 않다면 현재 front가 가리키는 위치의 값을 null로 비워준다.
• front에 1을 더해 포인터를 뒤로 이동시킨다.
• queue.length로 나눠주는 이유는 front 포인터가 큐의 끝까지 도달했을 때 맨 앞 위치로 돌려놓기 위해서이다.

<front 메서드 구현>

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return queue[front];
		}
	}

• 만약 큐가 비어 있으면 null값을 리턴한다.
• 그렇지 않다면 현재 front가 가리키는 위치의 값을 리턴한다.

<isEmpty 메서드 구현>

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• 원소의 개수가 0이면 true, 아니면 false를 리턴한다.

<dequeueAll 메서드 구현>

	@Override
	public void dequeueAll() {
		queue = (E[]) new Object[queue.length];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

• queue, front, tail, size값을 초기화한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		for (int i=tail; i>=front; i--) {
			System.out.print(queue[i]+" ");
		}
	}

• tail부터 front까지 순회하며 큐 원소 값을 출력한다.

- 전체 코드

public class ArrayQueue<E> implements QueueInterface<E> {

	
	//필드 영역
	private E queue[];
	
	private int front, tail, size;
	
	private static final int DEFAULT_CAPACITY = 64;
	
	//생성자 영역
	public ArrayQueue() {
		queue = (E[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	public ArrayQueue(int n) {
		queue = (E[]) new Object[n];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}
	
	//메서드
	
	public boolean isFull() {
		return (size==queue.length);
		
	}

	@Override
	public void enqueue(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			tail = (tail+1)%queue.length;
			queue[tail]=x;
			size++;
		}
	}

	@Override
	public void dequeue() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
		queue[front]=null;
		front=(front+1)%queue.length;
		size--;
		}
	}

	@Override
	public E front() {
		if (isEmpty()) {
			return null;
		} else {
		return queue[front];
		}
	}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void dequeueAll() {
		queue = (E[]) new Object[queue.length];
		front = 0;
		tail = DEFAULT_CAPACITY-1;
		size=0;
	}

	@Override
	public void printAll() {
		for (int i=tail; i>=front; i--) {
			System.out.print(queue[i]+" ");
		}
	}
}

 

3) 결과 확인하기

- 코드

public class Test {
	public static void main(String[] args) {
		
	
	ArrayQueue<Integer> lst = new ArrayQueue<>();
	
	lst.enqueue(100);
	
	lst.enqueue(200);
	
	lst.enqueue(300);
	
	lst.enqueue(400);
	
	lst.printAll();
	System.out.println();
	
	//ArrayQueue에 100,200,300,400을 순서대로 입력 후 현재 ArrayQueue 상태를 출력
	
	System.out.println(lst.front());
	
	//ArrayQueue의 가장 앞에 있는 값을 출력
	
	lst.dequeue();
	
	lst.printAll();
	
	System.out.println();
	
	//ArrayQueue의 가장 앞에 있는 값을 삭제하고 출력
	
	System.out.println(lst.isEmpty());
	
	//ArrayQueue가 비었는지 출력
	
	
	}
}

- 결과