/ PT

21 01 16

Collection 구조

Alt text

  • Queue를 상속하고 있는 Deque
  • Queue는 단방향으로 삽입삭제가 가능하다면 Deque은 양방향에서 삽입삭제가 가능

Queue/Deque Interface를 구현하는 클래스들

  1. LinkedList
  2. ArrayDeque
  3. Priority Queue

LinkedList Class

Alt text

큐의 정의

  • 큐의 사전적의미는 무엇을 기다리는 사람의 줄
  • FIFO (First In First Out, 선입선출), FCFS (First Come First Service)
  • 한쪽 끝에서는 삽입만 다른 한쪽 끝에서는 삭제만 발생

큐 주요 메소드 및 용어

Alt text

메소드 설명
Enqueue 큐에 데이터 삽입 하는 메서드
Dequeue 큐에 데이터 삭제 하는 메서드
isEmpty 큐가 empty 상태 인지 확인
isFull 큐가 full 상태 인지 확인
peek 큐의 첫번째 위치에 있는 데이터 추출
용어 설명
front, head 삭제가 발생하는 지점을 가르킨다.(포인터로 해석)
rear, tail 삽입이 발생하는 지점을 가르킨다.

배열로 큐 구현

public class ArrayQueue  {

    // 큐 배열은 front , rear , queue의 size를 가진다.
    private int front;
    private int rear;
    private int queueSize;
    private int queueArr[];

    // 생성자에서 초기화
    public ArrayQueue(int queueSize) {
        front = -1;
        rear = -1;
        this.queueSize = queueSize;    // queue 사이즈 설정
        this.queueArr = new int[this.queueSize];// 큐 배열 생성
    }

    // 큐가 비어있는 상태인지 확인
    public boolean isEmpty() {
        if(front == rear) {
            System.out.println("empty");
            return true;
        }else{
            return  false;
        }
    }

    // 큐가 가득찬 상태인지 확인
    public boolean isFull() {
        // rear 포인터가 큐의 마지막 인덱스와 동일하면 true 아니면 false
        return (rear == this.queueSize-1);
    }

    // 큐에 데이터 삽입 rear 증가
    public void enqueue(int item) {
      if(isFull()){
          throw new ArrayIndexOutOfBoundsException();
      }else {
            queueArr[++rear] = item;    // 다음 rear 포인터가 가리키는 위치에 데이터 추가
            System.out.println("Inserted Item : " + item);
        }
    }

    // 큐에서 데이터 추출 후 front 증가
    public void dequeue() {
        if(!isEmpty()) {
            ++front;
            System.out.println("Deleted Item : " + queueArr[front]);
        }
    }

    // 큐의 첫번째 데이터 추출
    public int peek() {
        if(!isEmpty()) {
            System.out.println("Peeked Item : " + queueArr[front + 1]);
        }
        return queueArr[front+1];
    }

    // 큐에 저장된 모든 데이터를 출력
    public void printQueue() {
        if(!isEmpty()) {
            System.out.print("Queue elements : ");
            for(int i=rear; i>=front+1; i--) {
                System.out.print(queueArr[i] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        int queueSize = 5;
        ArrayQueue arrQueue = new ArrayQueue(queueSize);

        arrQueue.isEmpty();
        arrQueue.enqueue(1);
        arrQueue.enqueue(2);
        arrQueue.enqueue(3);
        arrQueue.enqueue(4);
        arrQueue.enqueue(5);
        arrQueue.printQueue();


        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();
    }
}

enqueue 그림

Alt text

코드 결과

Alt text

  • enqueue 시 rear 1증가
  • dequeue 시 front 1증가

문제점

데이터가 다 차있지 않더라도 rear와 front가 계속 증가되다 보면 언젠가는 배열의 사이즈까지 도달하여 더이상 사용할 수 없게 된다는 문제점이 발생한다.
Alt text

원형, 환형 큐(Circular Queue)

  • 원형큐는 논리적으로 배열의 처음과 끝이 연결 되어있는 것으로 간주한다.
  • 공백상태와 포화 상태를 쉽게 구분하기위해 자리 하나를 항상 비워둔다.
  • 초기 상태에서는 rear, front 값이 0이 된다.

Alt text Alt text

우선순위 큐(Priority Queue)

  • 말그대로 ‘우선순위큐’ 우선순위가 가장 높은 데이터를 가장 먼저 삭제 하는 자료구조

  • 구현방법
    1. 리스트를 이용하여 구현
    2. 힙(heap)을 이용하여 구현
  • heap의 특징
    • 완전 이진 트리 자료구조
    • 힙에서는 항상 루트 노드(root node)를 제거
    • 최소 힙(min heap)
      • 루트 노드가 가장 작은 값을 가집니다.
      • 따라서 값이 작은 데이터가 우선적으로 제거
    • 최대 힙(max heap)
      • 루트 노드가 가장 큰 값을 가집니다.
      • 따라서 값이 큰 데이터가 우선적으로 제거됩니다.
  • 완전 이진 트리
    • root 노드 부터 시작하여, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 데이터가 차례대로 삽입되는 트리(tree)를 의미합니다.
  • Min-Heapify()
    • 어떤한 데이터를 힙(heap)에 넣었을 때 힙자료구조가 힙의 성질을 가질때 필요! -Heapify : 일반적으로 힙을 구성하는 함수의 이름을 말한다. -상향식 -하양식

Deque 데크

  • 양쪽 큐 끝에서 삽입삭제가 모두 발생 할 수있는 큐
  • 삽입 삭제가 용이, 데이터 중간

References.