큐(Queue)
먼저 넣은 데이터가 먼저 나오는 FIFO(First in First out) 구조로 저장하는 자료 구조
(이미지 출처 : https://buildgoodhabit.tistory.com/142)
연산
- enQueue : 큐에 요소를 추가한다. rear + 1 을 하고 그 자리에 요소를 추가한다.
- deQueue : 큐에서 맨 앞의 요소를 제거한다. front + 1 을 하고 그 자리에 있던 요소를 출력한다.
- isEmpty : 큐가 비었는지를 확인한다. front == rear이면 큐가 비었다고 판단한다.
- peek : 큐의 맨 앞의 요소를 확인한다.
구현
- Array
public static class ArrayQueue {
private int front, rear, size;
private int capacity;
private int array[];
public ArrayQueue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
public boolean isFull(ArrayQueue queue) {
return queue.size == queue.capacity;
}
public boolean isEmpty(ArrayQueue queue) {
return queue.size == 0;
}
public void enqueue(int item) {
if (isFull(this)) return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size++;
System.out.println(item + " enqueued to queue");
}
public int dequeue() {
if (isEmpty(this)) return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size--;
return item;
}
public int getFront() {
if (isEmpty(this)) {
return Integer.MIN_VALUE;
}
return this.array[this.front];
}
public int getRear() {
if (isEmpty(this)) {
return Integer.MIN_VALUE;
}
return this.array[this.rear];
}
}- 시간복잡도
- Enqueue(insertion) : O(1)
- Dequeue(deletion) : O(1)
- Front(Get front) : O(1)
- Rear(Get rear) : O(1)
- 공간 복잡도
- O(N)
- 배열 구현의 장점
- 구현이 간단하다.
- 배열 구현의 단점
- 사이즈가 고정되어 있다.
- 사이즈가 고정되어 있다.
- Linked List
public static class QNode {
int key;
QNode next;
public QNode(int key) {
this.key = key;
this.next = null;
}
}
public static class LinkedListQueue {
private QNode front, rear;
public LinkedListQueue() {
this.front = this.rear = null;
}
public void enqueue(int key) {
QNode temp = new QNode(key);
if (this.rear == null) {
this.front = this.rear = temp;
return;
}
this.rear.next = temp;
this.rear = temp;
}
public void dequeue() {
if (this.front == null) {
return;
}
QNode temp = this.front;
this.front = this.front.next;
if (this.front == null) {
this.rear = null;
}
}
}- 시간복잡도
- enqueue, dequeue : O(1)
Priority Queue
- 특징
- 모든 항목에는 연관된 우선순위가 있다.
- 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 큐에서 제거한다.
- 두 요소의 우선 순위가 같으면 대기열의 순서에 따라 제공된다.
Dequeue (Double - ended Queue)
- 특징
- Dequeue는 양쪽에서 넣고 빼고가 가능한 큐이다.
- Dequeue는 Stack과 Queue를 합쳐놓은 것과 같다.
- pushFront + popBack = Stack, pushBack + popFront = Queue
public class MyDequeue {
private MyNode front, rear;
public void pushFront(int data) {
if (front == null) {
this.front = this.rear = new MyNode(data);
} else {
MyNode temp = new MyNode(data);
temp.next = this.front;
this.front.prev = temp;
this.front = temp;
}
System.out.println(data + " front pushed to dequeue");
}
public void pushBack(int data) {
if (rear == null) {
this.front = this.rear = new MyNode(data);
} else {
MyNode temp = new MyNode(data);
temp.prev = this.rear;
this.rear.next = temp;
this.rear = temp;
}
System.out.println(data + " back pushed to dequeue");
}
public int popFront() {
if (this.front == null) {
System.out.println("Empty Dequeue");
return -1;
}
MyNode temp = this.front;
this.front = this.front.next;
this.front.prev = null;
return temp.data;
}
public int popBack() {
if (this.rear == null) {
System.out.println("Empty Dequeue");
return -1;
}
MyNode temp = this.rear;
this.rear = this.rear.prev;
this.rear.next = null;
return temp.data;
}
public class MyNode {
MyNode prev;
MyNode next;
int data;
MyNode(int data) {
this.data = data;
}
}
}참고
새싹 개발자