Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- geometry
- Tree
- Counting
- Binary Tree
- Math
- Class
- 자바
- Method
- sorting
- database
- string
- 파이썬
- greedy
- bit manipulation
- Data Structure
- two pointers
- Number Theory
- dynamic programming
- 구현
- 코테
- java
- SQL
- Stack
- Matrix
- implement
- hash table
- Binary Search
- 코딩테스트
- simulation
- array
Archives
- Today
- Total
코린이의 소소한 공부노트
큐(queue) 본문
1. 개념정리
1) 뒤쪽에서는 삽입이, 앞쪽에서는 삭제가 일어나는 구조
2) FIFO(First In First Out, 첫 삽입 데이터가 먼저 삭제됨)
3) java.util 패키지에 Queue 인터페이스가 있고, 이를 구현한 클래스 중 대표적인 것이 LinkedList가 있다.
2. 구현 코드
class ArrayQueue{ // int[]로 구현하는 큐
protected final int defCap = 100; // 큐의 용량
protected int[] queue; // 큐로 사용할 배열
protected int numElements = 0; // 큐에 들어간 요소의 개수
protected int front = 0; // 큐의 맨 앞 인덱스
protected int rear; // 큐의 맨 뒤 인덱스
public ArrayQueue() { // 기본 생성자
queue = new int[defCap];
rear = defCap -1;
}
public ArrayQueue(int maxSize) { // 큐의 크기를 지정한 생성자
queue = new int[maxSize];
rear = maxSize -1;
}
public void enqueue(int element) throws Exception { // 큐의 맨 뒤에 요소 추가
if (isFull()) // 큐가 가득 찼다면 에러 발생
throw new Exception("full queue: enqueue 실패 -> " + element);
else{
rear = (rear + 1) % queue.length;
queue[rear] = element;
numElements += 1;
}
}
public int dequeue() throws Exception{ // 큐의 첫 번째 요소 제거
if (isEmpty()) // 큐가 비어있다면 에러 발생
throw new Exception("empty queue: dequeue 실패");
else{
int toReturn = queue[front];
queue[front] = 0;
front = (front + 1) % queue.length;
numElements -= 1;
return toReturn;
}
}
public boolean isEmpty() { // 큐가 비어있다면 true 반환
return (numElements == 0);
}
public boolean isFull() { // 큐가 가득 찼다면 true 반환
return (numElements == queue.length);
}
public int size() { // 큐에 들어있는 요소의 개수 반환
return numElements;
}
public int capacity() { // 큐의 용량 반환
return queue.length;
}
}
3. 예제 코드
// 1) 생성
ArrayQueue queue = new ArrayQueue(10); // 크기를 정하는 큐
ArrayQueue queue2 = new ArrayQueue(); // 기본 생성자로 만드는 큐
// 2) 추가
for(int i=1 ; i<=queue.capacity() ; i++)
queue.enqueue(i);
// queue = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// 3) 삭제
for(int i=0 ; i<5 ; i++)
System.out.print(queue.dequeue() + " ");
// 1 2 3 4 5
// queue = [6, 7, 8, 9, 10]
'Back-End > Data Structure' 카테고리의 다른 글
세그먼트 트리(Segment tree) (0) | 2023.07.04 |
---|---|
이진 탐색 트리 (0) | 2023.04.15 |
스택 (stack) (0) | 2023.03.13 |
연결 리스트(linked list) (0) | 2023.03.10 |
배열 (array) (0) | 2023.03.09 |