일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- Database
- 오라클
- 클라우드
- 리눅스
- 쿼리최적화
- 서버
- 개발방법론
- 리눅스공부
- EC2
- JDBC
- AWS
- 트랜잭션
- 컴퓨터
- 데이터베이스프로그래밍
- 클라우드네이티브
- 시스템프로그래밍
- dbms
- 데브옵스
- jdbc programming
- sql
- 쿼리
- 데이터베이스
- 개발자
- 자바
- CS
- 명령어
- 개발공부
- TDD
- 공부
- DB
Archives
- Today
- Total
개발 블로그
큐(Queue) 본문
Queue
선입선출(First In First Out; FIFO)의 자료구조로 대기열이라고도 한다
가장 먼저 들어온 데이터가 가장 먼저 나가는 구조
삽입은 맨 뒤에서만 이루어지고, 삭제는 맨 앞에서만 이루어지는 구조, 중간에 끼워넣기 X
Queue 용어
- enqueue(data) : 큐의 맨뒤에 데이터 삽입
- dequeue: 큐의 맨앞 데이터 삭제 및 반환
- front : 큐의 맨앞 데이터
- rear(back): 큐 맨뒤 데이터
- size: 큐 크기
- 가득찬 큐에 데이터를 삽입하려고 시도하면 overflow, 빈 큐에서 데이터를 삭제하려고 시도하면 underflow 발생
Queue 구현
Java에서 큐는 array나 LinkedList로 구현할 수 있음, 각자 장단점이 다름
1) Array로 구현
배열로 구현 시 구현은 쉽지만, 크기가 동적이지 못하다.
배열을 선언할 때 크기를 지정해줘야하기 때문에 크기를 런타임에 바꿀 수 없다. front와 rear를 관리해줘야한다.
public class ArrayQueue{
int[] queue;
int front;
int rear;
int size;
public ArrayQueue(int size){
queue = new int[size];
this.size = size;
this.front = 0;
this.rear = -1;
}
public void enqueue(int data){
if(isFull()){
//overflow...
}else{
queue[++rear] = data;
size++;
}
}
public int dequeue(){
if(isEmpty()){
//underflow...
return -1;
}else{
size--;
return queue[front++];
}
}
public boolean isFull(){
return rear == size;
}
public boolean isEmpty(){
return size == 0;
}
}
2) Linked List로 구현
Queue<Integer> queue = new LinkedList<>();
위처럼 선언하여 사용할 수 있다. 연결 리스트를 사용하면 큐 사이즈를 동적으로 관리할 수 있고, 삽입 및 삭제 연산 등은 LinkedList에 내장 함수를 사용하면 된다.
enqueue 연산은 add나 offer 함수를 사용하면 된다.
//enqueue
queue.add(1);
queue.offer(2);
dequeue 연산은 poll이나 remove 함수를 사용하면 된다.
//dequeue
queue.poll();
queue.remove();
그 외의 isEmpty나 검사 함수는 아래와 같다.
queue.isEmpty(); //queue가 비어있는지 확인
queue.element(); //queue의 front 원소 반환, queue가 비어있으면 excetion 반한
queue.peek(); //queue의 front 원소 반환, queue가 비어있으면 null 반환