Queue?
위 그림의 왼쪽처럼 식당에 입장하기 위해 줄을 서는 것을 생각해보면 가장 먼저 줄을 선 사람이 가장 먼저 입장한다.
Queue도 이와 같은 방식으로 동작한다.
이처럼 먼저 들어간 것이 먼저 나오는 것을 선입선출(First In First Out, FIFO)라고 한다.
Queue의 주요 연산 Enqueue와 Dequeue
- Enqueue(): 값을 집어넣는 것을 의미
- Dequeue(): 값을 꺼내는 것을 의미
Java에서 Queue의 Enqueue와 Dequeue 메소드
- Enqueue: add, offer
- Dequeue: remove, poll
Queue의 시간복잡도
- Enqueue(): O(1)
- Dequeue(): O(1)
- 탐색: O(n)
Queue에서 값을 탐색하여 얻는 것은 부적절하다. 실제로 Java에서 Queue의 메소드 중 index나 특정 값을 탐색하는 메소드는 존재하지 않는다. 따라서 값을 탐색해야할 경우에는 리스트 또는 배열을 사용하는 것이 좋다.
구현
public class MyQueue<T> {
private Object[] array;
private int size; //요소의 개수
private int front; //가장 앞 쪽에 있는 요소의 위치
private int rear; //가장 뒤 쪽에 있는 요소의 위치
private int capacity; //큐의 전체 용량
public MyQueue(int capacity) {
this.capacity = capacity;
this.array = new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = -1;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
public void enqueue(T item) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue.");
return;
}
rear = (rear + 1) % capacity; //capacity=5, rear=4일 때 다음 rear는 0
array[rear] = item;
size++;
}
public T dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return null;
}
T item = (T) array[front];
front = (front + 1) % capacity; //capacity=5, front=4일 때 다음 front 0
size--;
return item;
}
public T peek() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot peek.");
return null;
}
return (T) array[front];
}
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println("Front of the queue: " + queue.peek());
System.out.println("Dequeue: " + queue.dequeue());
System.out.println("Dequeue: " + queue.dequeue());
queue.enqueue(4);
queue.enqueue(5);
System.out.println("Front of the queue: " + queue.peek());
System.out.println("Queue size: " + queue.size());
System.out.println("Dequeue: " + queue.dequeue());
System.out.println("Dequeue: " + queue.dequeue());
System.out.println("Dequeue: " + queue.dequeue());
System.out.println("Is queue empty? " + queue.isEmpty());
//output:
// Front of the queue: 1
// Dequeue: 1
// Dequeue: 2
// Front of the queue: 3
// Queue size: 3
// Dequeue: 3
// Dequeue: 4
// Dequeue: 5
// Is queue empty? true
}
}