Introduction
스택을 했으니... 이제는 큐를 할 차례입니다. 대표적인 자료구조 중 하나인 큐에 대해 알아봅니다.
Queue?
Stack은 후입선출(Last-In-First-Out) 자료구조입니다. 큐(Queue)는 선입선출(First-In-First-Out) 자료구조입니다. 즉 먼저 들어간 것이 먼저 나오는 구조입니다.
동작 원리
동작 원리를 설명하기에 앞서, 큐는 스택과 달리 두 가지의 포인터가 존재합니다. 맨 앞을 나타내는 front 포인터, 맨 뒤를 나타내는 rear 포인터입니다.
front에서는 자료가 나갈 때 포인터가 변경이 됩니다. 그리고 rear는 자료가 들어올 때 포인터가 변경이 됩니다. 즉 스택에서의 그림과는 달리 들어오는 곳과 나오는 곳이 서로 다릅니다.
큐의 연산을 정리하면 아래와 같습니다.
enqueue X: X를 큐에 넣는 연산dequeue: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 반환.size: 큐에 들어있는 정수의 개수를 반환isEmpty: 큐가 비어있으면 true, 아니면 false 반환peek: 큐의 가장 앞에 있는 정수를 반환.
다른 연산은 크게 스택과 많이 달라보이지는 않고 직관적인데, enqueue와 dequeue는 뭔가 특이해 보입니다. 한번 알아보도록 하겠습니다.
Queue의 활용
- 너비 우선 탐색(BFS)
- 프린터 출력 처리
- 티켓팅 등 대기열
- 비동기 함수 실행 시 테스크 규
enqueue
동작 원리에서 언급하였듯, enqueue는 rear가 변경되는 연산입니다. 설명보다 그림으로 보면 이해가 편하므로 그림으로 살펴보겠습니다.
그림을 보면 rear(뒤) 부분에 자료가 추가되어 포인터가 변경되는 것을 확인할 수 있습니다.
dequeue
동작 원리에서 언급하였듯, dequeue는 front가 변경되는 연산입니다. 설명보다 그림으로 보면 이해가 편하므로 그림으로 살펴보겠습니다.
그림을 보면 front(앞) 부분에 자료가 추가되어 포인터가 변경되는 것을 확인할 수 있습니다.
시간복잡도
모든 연산에서 시간복잡도는 O(1)입니다. size의 경우 따로 필드에서 값을 가지고 있는 상태로 계산하면 되고, 나머지 연산은 필요한 포인터에서 상에서만 진행하면 되고 다른 데이터, 노드들은 전부 비교할 필요가 없기에 그렇습니다.
원형 큐
원형 큐(Circular Queue)의 경우 크기가 제한 되어있는 큐로, 만약 자료가 가득찰 경우에는 마지막 노드가 첫번째 노드와 연결되게 됩니다. 마치 뱀이 본인 꼬리를 무는 듯한 모양새가 나오게 됩니다. 그 외에는 일반 큐(선형 큐)와 동일합니다.
구현
MyQueue Interface
직접 클래스로 구현해도 되지만, Circular Queue까지 진행하기 위해 인터페이스로 먼저 뼈대를 구성하였습니다. 사용하는 메소드들은 큐의 연산들입니다.
/*
* enqueue X: 정수 X를 큐에 넣는 연산
* dequeue: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 반환. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 반환(원래는 Exception)
* size: 큐에 들어있는 정수의 개수를 반환
* isEmpty: 큐가 비어있으면 true, 아니면 false 반환
* peek: 큐의 가장 앞에 있는 정수를 반환. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 반환(원래는 Exception)
*/
public interface MyQueue {
void enqueue(int x);
int dequeue();
int size();
boolean isEmpty();
int peek();
}MyQueueImpl
기본적인 큐인 선형 큐(앞서 작동원리까지 설명한 큐가 바로 선형 큐입니다.) 입니다. main 메소드 만들어서 테스트까지 한번에 진행한 코드입니다. 기본적으로 연결 리스트 만들 때 사용했던 내용을 많이 참고해서 구현했습니다.
class MyQueueImpl implements MyQueue {
private int size;
private Node front;
private Node rear;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public MyQueueImpl() {
this.size = 0;
this.front = null;
this.rear = null;
}
@Override
public void enqueue(int x) {
Node node = new Node(x);
if(size == 0) {
this.front = node;
} else {
node.prev = this.rear;
this.rear.next = node;
}
this.rear = node;
size++;
}
@Override
public int dequeue() {
if(size == 0) {
System.out.print("Fail. Return ");
return -1;
}
Node node = this.front;
this.front = node.next;
size--;
return node.data;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
@Override
public int peek() {
if(size == 0) {
System.out.print("Fail. Return ");
return -1;
}
return this.front.data;
}
}
public class MyQueueRun {
public static void main(String[] args) {
MyQueue queue = new MyQueueImpl();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 1
System.out.println(queue.dequeue()); // 2
System.out.println(queue.peek()); // 3
System.out.println(queue.size()); // 1
System.out.println(queue.isEmpty()); // false
System.out.println(queue.dequeue()); // 3
System.out.println(queue.size()); // 0
System.out.println(queue.isEmpty()); // true
System.out.println(queue.dequeue()); // Fail. Return -1
System.out.println(queue.size()); // 0
}
}MyCircularQueue
원형에 초점을 맞추어 우선 상수로 지정된 크기(LIMIT)를 정해주고, size가 LIMIT이라면 front와 rear를 서로 연결해주는 방식으로 구현하였습니다.
class MyCircularQueue implements MyQueue{
private int size;
private Node front;
private Node rear;
private static final int LIMIT = 4;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public MyCircularQueue() {
this.size = 0;
this.front = null;
this.rear = null;
}
@Override
public void enqueue(int x) {
Node node = new Node(x);
if(this.size == 0) {
this.front = node;
this.rear = node;
size++;
return;
}
if(this.size == LIMIT) {
System.out.println("FULL!!");
return;
}
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
if(this.size == LIMIT - 1) {
this.rear.next = this.front;
this.front.prev = this.rear;
}
this.size++;
}
@Override
public int dequeue() {
if(this.size == 0) {
System.out.print("Fail. Return ");
return -1;
}
Node node = this.front;
this.front = node.next;
if(this.size == LIMIT) {
this.rear.next = null;
}
this.size--;
return node.data;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
@Override
public int peek() {
if(this.size == 0) {
System.out.print("Fail. Return ");
return -1;
}
return this.front.data;
}
}
public class MyCircularQueueRun {
public static void main(String[] args) {
MyQueue queue = new MyCircularQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.size()); // 3
queue.enqueue(4);
queue.enqueue(5); // FULL!!
System.out.println(queue.size()); // 4
System.out.println(queue.dequeue()); // 1
System.out.println(queue.peek()); // 2
System.out.println(queue.dequeue()); // 2
System.out.println(queue.dequeue()); // 3
System.out.println(queue.isEmpty()); // false
System.out.println(queue.dequeue()); // 4
System.out.println(queue.isEmpty()); // true
System.out.println(queue.dequeue()); // Fail. Returns -1
}
}