✅ 자료구조 : 데이터를 저장하는 방식
✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조
랜덤 접근 불가능?
모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들
큐 (Queue)
먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 자료구조. 즉, 스택과 반대이다.
큐의 추상화 연산
- enqueue(item) : item을 큐의 맨 뒤쪽에 추가
- dequeue() : 큐의 맨 앞쪽의 데이터 삭제
- peek() : 큐의 맨 앞 데이터를 반환
- isfull() : 큐가 가득 찼는지 확인
- isempty() : 큐가 비어 있는지 확인
큐의 구현
1. 배열을 이용한 구현
public class ArrayQueue {
int MAX = 1000;
int front; //머리 쪽에 위치할 index값, pop할때 참조하는 index
int rear; //꼬리 쪽에 위치할 index값, push할때 참조하는 index
int [] queue;
public ArrayQueue() {
front = rear = 0; //초기값 0
queue = new int[MAX]; //배열 생성
}
public boolean queueisEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
return front == rear;
}
public boolean queueisFull() { //queue가 가득 차 공간이 없는지 판단하는 함수
if(rear == MAX-1) {
return true;
}else
return false;
}
public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
return front-rear;
}
public void push(int value) {
if(queueisFull()) {
System.out.println("Queue is Full");
return;
}
queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
}
public int pop() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return -1;
}
int popValue = queue[front++];
return popValue;
}
public int peek() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return -1;
}
int popValue = queue[front];
return popValue;
}
}
2. LinkedList로 구현
public class QueueNode {
int value; //값을 넣음
QueueNode queueNode; //다음 노드를 가리킴
public QueueNode(int value) {
this.value = value;
queueNode = null;
}
public int getValue() {
return value;
}
public QueueNode getNextNode() {
return queueNode;
}
public void setNextNode(QueueNode queueNode) {
this.queueNode = queueNode;
}
}
public class QueueNodeManager{ //큐의 기능을 만들 클래스
QueueNode front,rear;
public QueueNodeManager() {
front = rear = null;
}
public boolean queueisEmpty() {
if(front == null && rear == null) {
return true;
}else {
return false;
}
}
public void push(int value) {
QueueNode queueNode = new QueueNode(value);
if(queueisEmpty()) { //큐안에 데이터가 없으면 첫번째 Node에 front와 rear를 연결
front = rear = queueNode;
}else {
front.setNextNode(queueNode); //큐 안에 데이터가 있으면 front를 다음 노드에 연결 후 front의 값을 마지막 노드로 삽입
front = queueNode;
}
}
public QueueNode pop() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return null;
}else {
QueueNode popNode = rear;
rear = rear.getNextNode();
return popNode;
}
}
public QueueNode peek() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return null;
}else {
return rear;
}
}
public int size() {
QueueNode front2 = front;
QueueNode rear2 = rear;
int count = 0;
while(front2 != rear2 && rear2 !=null) { //큐가 비어있는 경우가 있을수도 있을때도 생각해야함
count++;
rear2 = rear2.getNextNode();
}
return count;
}
}
사실 간단하게 하면 이렇게도 가능하다.
import java.util.Queue;
public class Queue {
Queue<Integer> queue = new LinkedList<>();
void enQueue(int n){
queue.add(n);
}
int deQueue(){
return queue.poll();
}
}
3. 배열과 리스트 구현의 차이
| 배열 큐 | LinkedList 큐 | |
| 장점 | 구현하기 쉽고, 데이터의 삽입 및 삭제가 간단하다. |
크기(데이터의 양)가 한정되어 있지 않고, 원하는 기능을 넣을 수 있다. |
| 단점 | 배열의 크기가 정해져 있어서 다 차버리면 사용할 수 없다. |
구현이 어렵고, 포인터를 위한 추가 메모리 공간이 필요하다. |
큐의 사용 사례
- 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.
- ex) CPU 스케줄링, 디스크 스케줄링
- 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 사용. (비동기 전송)
- ex) IO 버퍼, 파이프, 파일 IO
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
- 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
- 노드를 접근한 순서대로 처리할 수 있다.
- 캐시(Cache) 구현
- 우선순위가 같은 작업 예약 (인쇄 대기열)
- 선입선출이 필요한 대기열 (티켓 카운터)
- 콜센터 고객 대기시간
- 프린터의 출력 처리
- 윈도 시스템의 메시지 처리기
- 프로세스 관리
출처
- https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80_%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B3%BC%ED%95%99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88
- https://yoongrammer.tistory.com/46
- https://go-coding.tistory.com/6
- https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html
