3. 큐 Queues

• Queues란?
  FIFO(First In, First Out) 선입 선출
  리스트의 제한된 형태 : 한쪽 끝에서만 넣고, 다른 쪽 끝에서만 뺀다.
  Enqueue(넣기) Dequeue(빼기) Front(맨 앞의 값) Rear(맨 뒤의 값)
  
• Array-based Queue의 경우
  
  

       다음과 같이 계속해서 사용하게 되면, 배열의 한쪽 끝으로 점점 이동하게 된다는 문제점이 있다. 따라서

       아래와 같이 실행하였을 때, 영구적으로 배열을 사용할 수 있게 된다.

       그림처럼 배열을 원이라고 생각하고, 한쪽 끝으로 점점 이동했을 때, 다시 맨 앞으로 돌아가서 재활용하는 방법을 사용하면 된다.

       이를 코드로 생각해보면, 아래의 코드처럼 사용할 수 있다.

enqueue(E item){
    rearIdx = (rearIdx+1) % size; 계속 배열의 사이즈만큼 나눠서 삽입을 하면 됨.
    curr[rearIdx] = item;
}

       하지만 여기서 주의해야할 것이 하나가 있는데, 배열을 사용하여 Circular Queue를 구현하는 경우 배열이 꽉차서 배열을 더블링하게         되어 채워넣을 때 주의해야할 것이 있다.

9

10

3(front, rear)

8

       다음과 같은 Circular Queue가 있다. 해당 queue를 단순하게 더블링을 해보는 코드를 작성해보자.

if (size == data.length)
		data = Arrays.copyOf(data, data.length * 2);

       다음과 같이 코드를 작성하게 된 것을 표로 그려본다면,

9

10

3(front,rear)

8

       와 같이 작성이 될 것이다. 
       위와 같은 표가 아닌,

3(front)

8

9

10(rear)

       와 같이 표를 만들려면 아래와 같이 해야한다.

if (size == data.length) {
			E[] data2 = (E[]) new Object[data.length * 2];

			for (int i = 0; i < data.length; i++) {
				data2[i] = data[(front + i) % data.length];
			}
			data = data2;

			front = 0;
			rear = size;
		}

		data[rear] = item;
		rear = (rear + 1) % data.length;
		size++;

       새로운 배열 data2를 원래 data의 길이의 두배로 더블링하여 만들어, 인덱스 0부터 data의 front부터 rear까지 값을 넣도록 하는 것       이다.

---

      구현하기 [JAVA]

import java.util.Arrays;
import java.util.Random;

interface MyQueue<E> {
	public void clear();

	public void enqueue(E item);

	public E dequeue();

	public E front();

	public int length();
}

class AQueue<E> implements MyQueue<E> {
	private static int DEFAULT_CAPACITY = 10;
	E[] data;
	int front, rear, size;

	public AQueue() {
		data = (E[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		rear = 0;
		size = 0;
	}

	public void clear() {
		front = 0;
		rear = 0;
		size = 0;
	}

	public void enqueue(E item) {
		if (size == data.length) {
			E[] data2 = (E[]) new Object[data.length * 2];

			for (int i = 0; i < data.length; i++) {
				data2[i] = data[(front + i) % data.length];
			}
			data = data2;

			front = 0;
			rear = size;
		}

		data[rear] = item;
		rear = (rear + 1) % data.length;
		size++;
	}

	public E dequeue() {
		if (size == 0)
			return null;
		else {
			E ret = data[front];
			front = (front + 1) % data.length;
			size--;
			return ret;
		}
	}

	public E front() {
		if (size == 0)
			return null;
		return data[front];
	}

	public int length() {
		return size;
	}

}

class Solution {
	public int solution(int[] nums) {
		AQueue<Integer> queue = new AQueue<>();

		int checksum = 0;

		for (int n : nums) {
			if (n >= 0) {
				queue.enqueue(n);
				checksum += n;
				checksum %= 7919;
			} else {
				int x = queue.dequeue();
				checksum += x;
				checksum %= 7919;
			}
			checksum += queue.length();
			checksum %= 7919;
		}

		checksum += queue.length();
		checksum %= 7919;

		queue.clear();
		checksum += queue.length();
		checksum %= 7919;

		return checksum;
	}
}

• dequeue를 할 때도, front++;를 하는 것이 아닌, 길이만큼 나눈 나머지가 그 인덱스에 들어간다는 점을 잊지 말자.