[자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 큐(Queue)

이진이·2023년 8월 10일

data structure

✅ 자료구조 : 데이터를 저장하는 방식

✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조

랜덤 접근 불가능?

모든 자료에 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://jinijana.tistory.com

이전 포스트

[자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 스택(Stack)

다음 포스트