Queue
먼저 넣은 데이터가 먼저 나오는 형태(선입선출)의 자료구조를 의미한다. (First - In - First - Out)
가장 뒤에 원소가 추가되고, 가장 앞에 원소가 처리된다.
예를 들어, 티겟팅 대기열, 프린터 출력, 운영체제 스케줄링, 메세지 큐 등
Queue 역시 인터페이스로 구현 되어 있다.
Linked list 기반의 Queue
- enqueue: addLast를 사용해 리스트의 가장 앞 원소를 추가한다. (push)
- dequeue: removeFirst를 사용해 리스트의 가장 앞 원소를 삭제한다. (pop)
public class MyListQueue<E> {
private int size = 0;
private Node<E> frontNode = null;
private Node<E> rearNode = null;
public static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
tins.next = next;
}
}
// 가장 뒤 노드 추가
public void enqueue(E element) {
Node<E> newNode = new Node<>(element, null);
if (size == 0) frontNode = newNode;
else rearNode.next = newNode;
rearNode = newNode;
size++;
}
// 가장 앞 노드 제거
public void dequeue() {
if (size == 0) throw new NoSuchElementException("Queue is Empty");
E item = frontNode.item;
frontNode = frontNode.next;
if (frontNode == null)
rearNode = null;
size--;
return item;
}
}
import java.util.*;
public class MyListQueue<E> {
private int size = 0;
private Node<E> frontNode = null;
private Node<E> rearNode = null;
public static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
public void enqueue(E element) {
Node<E> newNode = new Node<>(element, null);
if (size == 0) frontNode = newNode;
else rearNode.next = newNode;
rearNode = newNode;
size++;
}
public E dequeue() {
if (size == 0)
throw new NoSuchElementException("Queue is empty.");
E item = frontNode.item;
frontNode = frontNode.next;
if (frontNode == null)
rearNode = null;
size--;
return item;
}
public E getFront() {
if (size == 0)
throw new NoSuchElementException("Queue is empty.");
return frontNode.item;
}
public E getRear() {
if (size == 0)
throw new NoSuchElementException("Queue is empty.");
return rearNode.item;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public static void main (String[] args) {
MyListQueue<Integer> q = new MyListQueue<>();
// 큐의 가장 뒤에 원소 추가: O(1)
q.enqueue(1); // [1]
q.enqueue(2); // [1, 2]
q.enqueue(3); // [1, 2, 3]
q.enqueue(4); // [1, 2, 3, 4]
// 큐의 가장 앞 원소 삭제: O(1)
q.dequeue(); // [2, 3, 4]
q.dequeue(); // [3, 4]
// 큐의 가장 앞/뒤 원소 조회: O(1)
System.out.println(q.getFront()); // 3
System.out.println(q.getRear()); // 4
}
}
Array 기반의 Queue
- enqueue: rearIndex에 원소를 추가하고, rearIndex를 이동한다.
- dequeue: firstIndex의 원소를 삭제하고, firstIndex를 이동한다.
public class MyArrauQueue<E> {
private Object[] data;
private int frontIndex;
private int rearIndex;
private int capacity;
private int size;
public MyArrayQueue(int maxCapacity) {
this.capacity = maxCapacity;
data = new Object[capacity];
frontIndex = 0;
rearIndex = -1;
size = 0;
}
// 가장 뒤 노드 추가
public boolean enqueue(E element) {
if (size == capacity) return false;
rearIndex = (rearIndex + 1) % capacity;
data[rearIndex] = element;
size++;
return true;
}
// 가장 앞 노드 삭제
public E deque() {
if (size == 0) return null;
E value = (e) data[frontIndex];
data[frontIndex] = null;
frontIndex = (frontIndex + 1) % capacity;
size--;
return value;
}
}
public class MyArrayQueue<E> {
private Object[] data;
private int frontIndex;
private int rearIndex;
private int capacity;
private int size;
public MyArrayQueue(int maxCapacity) {
this.capacity = maxCapacity;
data = new Object[capacity];
frontIndex = 0;
rearIndex = -1;
size = 0;
}
public boolean enqueue(E element) {
if (size == capacity) return false;
rearIndex = (rearIndex + 1) % capacity;
data[rearIndex] = element;
size++;
return true;
}
public E dequeue() {
if (size == 0) return null;
E value = (E) data[frontIndex];
data[frontIndex] = null;
frontIndex = (frontIndex + 1) % capacity;
size--;
return value;
}
public E getFront() {
if (size == 0) return null;
return (E) data[frontIndex];
}
public E getRear() {
if (size == 0) return null;
return (E) data[rearIndex];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public static void main (String[] args) {
// 고정 길이 배열을 사용하는 형태의 구현체에서는 최대 용량을 지정해야합니다.
MyArrayQueue<Integer> q = new MyArrayQueue<>(10);
// 큐의 가장 뒤에 원소 추가: O(1)
q.enqueue(1); // [1 ...]
q.enqueue(2); // [1, 2 ...]
q.enqueue(3); // [1, 2, 3 ...]
q.enqueue(4); // [1, 2, 3, 4 ...]
// 큐의 가장 앞 원소 삭제: O(1)
q.dequeue(); // [ 2, 3, 4 ...]
q.dequeue(); // [ 3, 4 ...]
// 큐의 가장 앞/뒤 원소 조회: O(1)
System.out.println(q.getFront()); // 3
System.out.println(q.getRear()); // 4
}
}
Queue의 사용예제
import java.util.*;
class Main
{
public static void main (String[] args) {
// FIFO 특성을 지닌 큐의 가장 기본적인 구현체인 LinkedList를 사용합니다.
Queue<Integer> q = new LinkedList<>();
// 큐의 가장 뒤에 원소 추가: O(1)
// 큐에 공간이 부족할 때 Exception이 발생하는 add와 false를 반환하는 offer가 제공됩니다.
q.offer(1); // [1]
q.offer(2); // [1, 2]
q.add(3); // [1, 2, 3]
q.add(4); // [1, 2, 3, 4]
// 큐의 가장 앞 원소 삭제: O(1)
// 큐가 비었을 때 Exception이 발생하는 remove와 null을 반환하는 poll이 제공됩니다.
q.poll(); // [2, 3, 4]
q.remove(); // [3, 4]
// 큐의 가장 앞 원소 조회: O(1)
// 큐가 비었을 때 Exception이 발생하는 element와 null을 반환하는 peek이 제공됩니다.
System.out.println(q.peek()); // 3
System.out.println(q.element()); // 3
}
}
[10845] 큐
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 0.5 초 (추가 시간 없음) | 256 MB | 145150 | 68878 | 54252 | 49.318% |
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
문제풀이
이 문제는 간단한 구현 문제이다. 직접 Queue class를 만들어서 작성해도 상관이 없다.
다만 나는 JAVA에 기본적으로 제공하는 Queue를 사용하여 풀어봤다.
0. 입출력
주어지는 명령의 수는 10000개 이하이지만 시간 제한이 0.5초이내이고 추후 100,000개의 명령어라면 입출력을 Scanner, System.out이 아닌 Buffered Reader와 Writer를 사용하는 것이 좋다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
. . .//code 줄임 표시
1. Queue 자료구조 이용하기
JAVA에서 구현된 자료구조를 사용하여 문제를 풀것이니 Queue<Integer> 타입을 갖고 있는 q 변수를 생성하자.
Queue<Integer> q = new LinkedList<>();
2. 조건에 맞는 메서드 사용하기
명령은 push 1 push 2 형태로 들어온다.
그러면 공백을 기준으로 분리하여 명령어와 넣을 data를 분리해주자.
나머지 add, remove, size, isEmpty, peek를 사용해주면 되지만 문제는 큐의 가장 뒤에 있는 원소를 가져오는 메서드가 없다.
| add(E e) | 원소를 큐에 추가 큐에 공간이 없다면 Exception 발생 | | --- | --- | | offer(E e) | 원소를 큐에 추가 큐에 공간이 없다면 false 반환 | | remove() | 큐의 head 원소를 제거하고 반환 큐가 비었다면 Exception 발생 | | poll() | 큐의 head 원소를 제거하고 반환 큐가 비었다면 null 반환 | | element() | 큐의 head 원소 반환 큐가 비었다면 Exception 발생 | | peek() | 큐의 head 원소 반환 큐가 비었다면 null 반환 |
lastValue를 이용하여 push 할때(add)마다 lastValue를 업데이트 해줘 출력해주자.
int lastValue = -1;
while(N-->0) {
String[] cmd = br.readLine().split(" ");
if(cmd[0].equals("push")) {
lastValue = Integer.parseInt(cmd[1]);
q.add(lastValue);
}
else if(cmd[0].equals("pop")) {
if (q.isEmpty())
bw.write("-1\\n");
else
bw.write(q.remove() + "\\n");
}
else if(cmd[0].equals("size")) {
bw.write(q.size() + "\\n");
}
else if(cmd[0].equals("empty")) {
bw.write(q.isEmpty() ? "1\\n" : "0\\n");
}
else if(cmd[0].equals("front")) {
bw.write(q.isEmpty() ? "-1\\n" : q.peek() + "\\n");
}
else if(cmd[0].equals("back")) {
bw.write(q.isEmpty() ? "-1\\n" : lastValue + "\\n");
}
}
bw.flush();
전체코드
import java.io.*;
import java.util.*;
class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Queue<Integer> q = new LinkedList<>();
int lastValue = -1;
while(N-->0) {
String[] cmd = br.readLine().split(" ");
if(cmd[0].equals("push")) {
lastValue = Integer.parseInt(cmd[1]);
q.add(lastValue);
}
else if(cmd[0].equals("pop")) {
if (q.isEmpty())
bw.write("-1\\n");
else
bw.write(q.remove() + "\\n");
}
else if(cmd[0].equals("size")) {
bw.write(q.size() + "\\n");
}
else if(cmd[0].equals("empty")) {
bw.write(q.isEmpty() ? "1\\n" : "0\\n");
}
else if(cmd[0].equals("front")) {
bw.write(q.isEmpty() ? "-1\\n" : q.peek() + "\\n");
}
else if(cmd[0].equals("back")) {
bw.write(q.isEmpty() ? "-1\\n" : lastValue + "\\n");
}
}
bw.flush();
}
}
[15828] Router
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 512 MB | 5932 | 3358 | 2794 | 58.501% |
문제
인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.
우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.
그림1. 네트워크에 존재하는 라우터들의 구성 예시
라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.
통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.
입력
첫 줄에는 라우터 내부에 존재하는 버퍼의 크기를 나타내는 자연수 N이 주어진다.
둘째 줄부터 한 줄에 하나씩 라우터가 처리해야 할 정보가 주어진다. 모든 정보는 발생한 시간순으로 주어졌다고 가정한다. 양의 정수는 해당하는 번호의 패킷이 입력으로 들어왔다는 것을 의미하고, 0은 라우터가 패킷 하나를 처리했다는 것을 의미한다. 이때, 버퍼가 비어있을때는 0이 입력으로 들어오지 않는다. -1은 입력의 끝을 나타낸다.
출력
라우터에 남아있는 패킷을 앞에서부터 순서대로 공백으로 구분해서 출력하면 된다. 만약 비어있을 경우 empty라고 출력한다.
Small (50점)
- 1 ≤ N ≤ 100,000
- 1 ≤ 정보의 수 ≤ N
Large (50점)
- 1 ≤ N ≤ 100,000
- 1 ≤ 정보의 수 ≤ 200,000
문제풀이
이 문제는 버퍼의 크기가 N인 라우터의 입력/처리 명령어를 차례로 처리 후 남아있는 패킷을 구하는 문제이다.
버퍼에 빈 공간이 없을 때 입력된 패킷은 버려진다.
router의 크기를 N으로 정하고 패킷은 N개 이하만 보관할 수 있다.
이 때 0이 들어오면 먼저들어온 패킷이 처리되는 상황이다.
크기 제한 배열 생성
router는 N개만큼의 크기를 갖고 있을 수 있다. 가변하지 않고 불변적인 배열을 만들자.
최대 정보 개수만큼 저장공간을 만들면 보관되는 패킷을 차례대로 기록하고 현재 남아있는 범위를 관리할 수 있다.
Queue 자료구조 사용
router는 선입선출로 패킷이 처리된다. Queue 자료구조를 이용하자.
위의 조건들을 만족하는 LinkedBlockingQueue를 사용하여 크기가 고정이고 Queue 자료구조 형태를 갖고 있는 배열을 만들었다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 버퍼의 크기
int N = Integer.parseInt(br.readLine());
Queue<Integer> router = new LinkedBlockingQueue<>(N);
조건에 맞게 분기 처리
조건문을 사용하여 명령에 맞게 알고리즘을 작성하자.
while(true) {
int cmd = Integer.parseInt(br.readLine());
if (cmd > 0) router.offer(cmd);
else if (cmd == 0) router.poll();
else break;
}
if (router.size() == 0) bw.write("empty");
else {
while(!router.isEmpty()) {
bw.write(router.poll() + " ");
}
}
bw.flush();
전체코드
import com.sun.jmx.remote.internal.ArrayQueue;
import java.io.*;
import java.sql.Array;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 버퍼의 크기
int N = Integer.parseInt(br.readLine());
Queue<Integer> router = new LinkedBlockingQueue<>(N);
while(true) {
int cmd = Integer.parseInt(br.readLine());
if (cmd > 0) router.offer(cmd);
else if (cmd == 0) router.poll();
else break;
}
if (router.size() == 0) bw.write("empty");
else {
while(!router.isEmpty()) {
bw.write(router.poll() + " ");
}
}
bw.flush();
}
}
시간복잡도
이 알고리즘의 시간복잡도는 O(N)이다.
'알고리즘 > Queue' 카테고리의 다른 글
| [코딩테스트] [1966] 프린터 큐 &[10866] 덱 (1) | 2025.01.22 |
|---|