[DataStructure/자료구조][CS] 3. Queue

devYeON_ 2021. 12. 28. 20:46

3. Queue

1. 정의

한쪽 끝에서 삽입이 이루어지고 반대쪽 끝에서는 삭제가 이루어지는 FIFO 형식의 유한 순서 리스트입니다.

2. 연산

연산	JAVA	설명
Enqueue	Offer	큐 맨뒤에 요소를 추가
Dequeue	Poll	큐 맨앞의 요소를 삭제
Peek	Peek	Front에 위치한 데이터를 읽음
Front		큐 맨앞에 위치한 인덱스를 읽음
Rear		큐 맨뒤에 위치한 인덱스를 읽음

3. 큐의 종류

① 선형 큐

일차원 배열
단점 : 값을 계속해서 넣으면 정해진 배열의 사이즈에 도달하게 되고 앞부분이 비더라도 사용하지 못함

소스코드

public class ArrayQueue{
	int max = 1000;
	int front;
	int rear;
	int[] q;
	public ArrayQueue(){
		front = 0;
		rear = 0;
		q = new int[max];
	}
	// queue가 비어있을 때
	public boolean isEmpty(){
		return front == rear;
	}
	// queue가 가득 찼을 때
	public boolean isFull(){
		if(rear == max-1)
			return true;
		else return false;
	}
	// queue 의 사이즈 반환
	public int size(){
		return front-rear;
	}
	// queue에 데이터 삽입
	public void push(int item){
		if(isFull()){
			System.out.println("IS FULL");
			return;
		}
		q[rear++] = item;
	}
	// queue의 데이터 삭제
	public int pop(){
		if(isEmpty()){
			System.out.println("IS EMPTY");
			return -1;
		}
		int value = q[front++];
		return value;
	}
	// queue의 최상단 데이터 조회
	public int peek(){
		if(isEmpty()){
			System.out.println("IS EMPTY");
			return -1;
		}
		int value = q[front];
		return value;
	}

② 원형 큐

선형 큐의 문제점을 해결하기 위한 구조
배열의 마지막 index에서 다음 index로 넘어갈 때, index+1 mod size를 이용해 OutOfBoundsException을 방지한다.

소스코드

public class CircleQueue{
	int rear = -1;
	int front = -1;
	int max = 1000;
	int count = 0;
	int[] q;

	public void push(int item){
		if(isFull()){
			System.out.println("IS FULL");
			return;
		}
		rear = (rear+1) % max;
		q[rear] = item;
		count++;	
	}
	public int pop(){
		if(isEmpty()){
			System.out.println("IS EMPTY");
			return -1;
		}
		front = (front+1) % max;
		count--;
		return q[front];
	}
	public int peek(){
		if(isEmpty()){
			System.out.println("IS EMPTY");
			return -1;
		}
		front = (front+1) % max;
		return q[front];
	}

③ Deque

큐의 양쪽에서 데이터를 삽입 삭제 할 수 있는 구조
연산
deque 연산

소스코드

public Node{
	int data;
	Node right;
	Node left;
}
public Deque{
	Node front;
	Node rear;
	public Deque(){
		front = null;
		rear = null;
	}
	public boolean isEmpty(){
			return front == rear;
	}
	public void addFront(int item){
		Node newNode = new Node();
		newNode.data = item;
		if(isEmpty()){
			front = newNode;
			rear = newNode;
			newNode.right = null;
			newNode.left = null;
		}else{
			front.left = newNode;
			newNode.right = front;
			newNode.left = null;
			front = newNode;
		}
	}
	public void addLast(int item){
		Node newNode = new Node();
		newNode.data = item;
		if(isEmpty()){
			front = newNode;
			rear = newNode;
			newNode.right = null;
			newNode.left = null;
		}else{
			front.right = newNode;
			newNode.right = null;
			newNode.left = rear;
			front = newNode;
		}
	}
	public int removeFront(){
		if(isEmpty()){
			return -1;
		}else{
			int item = front.data;
			if(front.right == null){
				front = null;
				rear = null;
			}
			else {
				front = front.right;
				front.left = null;
			}
		}
		return item;
	}
	public int removeLast(){
		if(isEmpty()){
			return -1;
		}else{
			int item = rear.data;
			if(front.left == null){
				front = null;
				rear = null;
			}
			else {
				front = front.left;
				front.right = null;
			}
		}
		return item;
	}

④ Priority Queue

들어간 순서에 상관없이 우선 순윅가 높은 데이터가 먼저 나오는 것
속성
- 모든 항목에는 우선순위가 있다
- 우선순위가 높은 요소는 낮은 요소보다 먼저 Queue에서 제외된다
- 두 요소의 우선순위가 같다면 Queue의 순서에 따라 제공된다
  priority queue 의 구조
구현 방식

① Array

- 소스코드

public class PriorityQueueImpl {

    public static int[] arr = {9, 1, 8, 3, 5, 6, 7, 4, 2};

    public static void main(String[] args) {
        Heap heap = new Heap();

        for (int i = 0; i < arr.length; i++)
            heap.push(arr[i]);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(heap.pop() + " "); // 1 2 3 4 5 6 7 8 9
        }
    }

    public static class Heap {
        int[] heap = new int[100];
        int count = 0;

        public Heap() {}

        public void push(int x) {
            heap[++count] = x;
            int index = count;
            while (index > 1 && heap[index / 2] > heap[index]) {
                if (index == 1 || heap[index / 2] < heap[index])
                    break;
                int tmp = heap[index / 2];
                heap[index / 2] = heap[index];
                heap[index] = tmp;
                index /= 2;
            }
        }

        public int pop() {
            int pop = heap[1];
            heap[1] = heap[count--];
            int index = 1;
            int next;
            while (true) {
                next = index * 2;
                if (next < count && heap[next] > heap[next + 1])
                    next++;
                if (next > count || heap[next] > heap[index])
                    break;
                int tmp = heap[index];
                heap[index] = heap[next];
                heap[next] = tmp;
                index = next;
            }
            return pop;
        }
    }
}

② Linked List

- 소스코드

import java.util.LinkedList;
import java.util.Queue;
 
public class ExampleQueue {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();//큐 생성
        queue.offer(5);//데이터를 집어 넣음
        queue.offer(1);//데이터를 집어 넣음
        queue.offer(2);//데이터를 집어 넣음
        queue.offer(3);//데이터를 집어 넣음
        queue.offer(4);//데이터를 집어 넣음
        print(queue);//큐를 출력
        System.out.println(String.format("poll: %d", queue.poll()));//poll
        System.out.println(String.format("poll: %d", queue.poll()));//poll
        System.out.println(String.format("poll: %d", queue.poll()));//poll
        System.out.println(String.format("peek: %d", queue.peek()));//peek
        System.out.println(String.format("peek: %d", queue.peek()));//peek
        
    }
    
    public static void print(Queue<Integer> queue) {
        System.out.print("data: ");
        queue.forEach((value)->{
            System.out.print(value);
        });
        System.out.println(String.format(" size: %d", queue.size())); 
    }
}

③ Heap

완전 이진 트리
배열로 구현
느슨한 정렬 상태

- 소스코드

package com.test;

public class PriorityQueueImpl<T extends Comparable>  {
    private Object array[];  // 데이터 저장 배열
    private static final int default_capacity = 1000001;  // 기본 100만개 데이터 넣을 수 있게 설정
    private int capacity;  // 사용자가 지정한 최대 데이터 입력 수
    private int size = 0;  // 현재 입력된 데이터 수
    private int lastIndex = 0; // 마지막으로 입력된 데이터의 Index

    public PriorityQueueImpl(){
        this.array = new Object[this.default_capacity];
        this.capacity = this.default_capacity;
    }

    public PriorityQueueImpl(int capacity){
        this.capacity = capacity+1;
        this.array = new Object[this.capacity];
    }

    public boolean insert(T data){
        if(capacity-1 == size){
            makeDouble();
        }
        array[++lastIndex] = data;

        aboveHeapify(lastIndex);
        size++;
        return true;
    }

    private void makeDouble(){
        this.capacity = this.capacity*2-1;
        Object newArray[] = new Object[this.capacity];

        System.arraycopy(this.array, 0, newArray, 0, this.lastIndex);
        this.array = newArray;
    }

    private void aboveHeapify(int startIndex){
        T relocateData = (T)this.array[startIndex];
        int current = startIndex;

        // Index가 Root에 다다르지 않았고 부모 데이터보다 현재 데이터가 더 크다면
        while(current > 1 && relocateData.compareTo((T)this.array[current/2]) > 0){
            // 부모 데이터를 현재 위치에 저장
            this.array[current] = this.array[current/2];
            current /= 2;
        }
        this.array[current] = relocateData;
    }

    public boolean isEmpty(){
        return this.size==0;
    }

    public T pop(){
        if(isEmpty()){
            throw new NullPointerException();
        }
        return pop((T)this.array[1]);
    }

    public T pop(T data){
        if(isEmpty()){
            throw new NullPointerException();
        }
        int targetIndex = find(data);

        // 만약 그런 데이터가 없다면
        if(targetIndex == -1){
            throw new NullPointerException();
        }

        // 반환할 데이터를 미리 저장
        T retData = (T)this.array[targetIndex];

        // 만약 가장 마지막에 저장된 데이터를 추출하려는 경우라면 그냥 추출하고 끝낸다.
        if(targetIndex == lastIndex){
            this.array[this.lastIndex--] = null;
            return retData;
        }

        // 가장 마지막에 저장된 데이터를 가져온다. 마지막 Index 값은 바꿔주어야 한다.
        T rightMostData = (T)this.array[this.lastIndex];
        this.array[this.lastIndex--] = null;


        // 최 우측 데이터를 현재 제거될 위치의 데이터가 있는 자리에 넣는다.
        this.array[targetIndex] = rightMostData;

        // 루트 데이터가 추출되는 경우이거나 부모 데이터보다 대체된 데이터가 더 작다면 아래로 Heapify
        if(targetIndex == 1 || rightMostData.compareTo((T)this.array[targetIndex / 2]) < 0){
            belowHeapify(targetIndex);

        // 아니라면 위로 Heapify
        } else {
            aboveHeapify(targetIndex);
        }

        return retData;
    }

    public int find(T data){
        for(int i=1; i < this.array.length; i++){
            if(this.array[i].equals(data)){
                return i;
            }
        }
        return -1;
    }

    private void belowHeapify(int startIndex){
        T relocateData = (T)this.array[startIndex];
        int current = startIndex;

        // 마지막 Index보다 작거나 같을 때까지 지속 진행
        while(current <= lastIndex){
            int leftIndex = current*2;
            int rightIndex = current*2+1;

            // 현재 Leaf 위치라면 더 이상 비교할 필요 없다.
            if(leftIndex > lastIndex){
                break;
            } else {
                T leftChild = (T)this.array[leftIndex];
                T rightChild = rightIndex > this.lastIndex ? null : (T)this.array[rightIndex];

                // 우측 자식이 없고 좌측 자식이 더 값이 크다면 상호 위치를 바꾼다.
                if(rightChild == null){
                    if(leftChild.compareTo(relocateData) > 0) {
                        this.array[current] = leftChild;
                        this.array[leftIndex] = relocateData;
                        current = leftIndex;
                    } else {
                        break;
                    }
                } else {
                    T targetToSwap = leftChild.compareTo(rightChild) > 0 ? leftChild : rightChild;
                    int swapIndex = leftChild.compareTo(rightChild) > 0 ? leftIndex : rightIndex;
                    if(targetToSwap.compareTo(relocateData) > 0){
                        this.array[current] = targetToSwap;
                        this.array[swapIndex] = relocateData;
                    }
                    current = swapIndex;
                }
            }
        }
    }
}

4. 시간복잡도

연산	Big-O
insert	O(1)
delete	O(1)
search	O(n)

	Array	LinkedList
insert	O(n)	O(1)
delete	O(1)	O(1)
search	O(1)	O(n)

5. 요약

	Array Queue	Array Circular Queue	Linked List Queue
구현	Array	Arrray	LinkedList
특징	계속 삽입을 할 경우, 앞의 메모리공간이 비어있는 상태로 방치됨. 즉, 메모리 손실 가능성이 있음.	Array Queue의 단점을 보완. rear이 배열의 마지막에 배치되어있고, 비어있는 메모리가 있을 경우, 앞으로 돌아와서 데이터를 삽입한다.	앞선 array 구현 방식의 큐는 배열의 단점인 정적 사이즈의 메모리다. 이를 LinkedList로 구현해 비어있는 메모리를 만들지 않아 더욱 효율적으로 사용 가능하다

저작자표시 (새창열림)