[면접을 위한 CS 전공지식 노트][자료구조] Queue(큐)

0. 개요

 이번에는 Queue에 대해서 공부한것을 글로 정리할 예정이다.

 

1. Queue

 큐는 FIFO(First In First Out)구조이다. 스택이 LIFO(Last In First Out) 였던 것과 대조적이다. CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시, 메시지큐 등에 사용된다.  큐 같은 경우 node를 이용해 만든 선형큐와 배열을 이용해 만든 원형큐가 있다.

 원형큐는 새로운 데이터를 offer 할 때마다 Rear 인덱스를 +1, poll 할 때마다 front+1에 있는 데이터를 꺼내고 front+1.

 

배열을 이용해 구현한 원형 큐에서의 상태 조건

 1) Rear와 Front가 같은 곳을 가리키고 있다. -> 큐가 비어 있다.

 2) mod 연산을 통해서 인덱스 계산 및 접근.

 3) Rear 다음 인덱스에 Front가 있다면 큐가 가득 차있음을 알 수 있다.

 

자료구조를 직접 구현 해보면서 이해를 해보았다.

 Queue의 기능을 명세한 인터페이스

offer: Queue에 data를 넣는다.

poll: 맨 앞 데이터를 꺼낸다.

peek: 맨 앞 데이터를 확인한다.

size: 현재 큐에 들어 있는 엘리먼트 갯수를 확인한다.

clear: 큐를 비운다.

isEmpty: 큐가 비어있는지 확인

public interface IQueue<T> {
    void offer(T data);
    T poll();
    T peek();
    int size();
    void clear();
    boolean isEmpty();
}

 

1) 선형큐

 node를 이용하여 구현

public class MyLinkedQueue<T> implements IQueue<T> {

    private Node head;
    private Node tail;
    private int size;

    public MyLinkedQueue() {
        this.head = new Node(null);
        this.tail = this.head;
        this.size = 0;
    }

    @Override
    public void offer(T data) {
        Node node = new Node(data);
        this.tail.next = node;
        this.tail = this.tail.next;
        size++;
    }

    @Override
    public T poll() {
        if(this.isEmpty()){
            throw new IllegalStateException();
        }
        Node node = this.head.next;
        head.next = node.next;
        node.next=null;
        this.size--;

        if (this.head.next == null) {
            this.tail = this.head;
        }
        return node.data;
    }

    @Override
    public T peek() {
        if(this.isEmpty()){
            throw new IllegalStateException();
        }
        return this.head.next.data;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {
        this.head.next = null;
        this.tail = this.head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next==null;
    }

    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

 

2) 원형 큐

 배열을 이용해 구현

public class MyCircularQueue<T> implements IQueue<T> {

    private T[] elements;
    private int front;
    private int rear;
    private int maxSize;

    public MyCircularQueue(int size) {
        this.elements = (T[]) new Object[size + 1];
        this.front = 0;
        this.rear = 0;
        this.maxSize = size+1;
    }

    @Override
    public void offer(T data) {
        if (isFull()){
            throw new IllegalStateException();
        }
        rear = (rear + 1) % maxSize;
        elements[rear] = data;
    }

    @Override
    public T poll() {
        if(isEmpty()){
            throw new IllegalStateException();
        }
        front = (front+1) % maxSize;
        return elements[front];
    }

    @Override
    public T peek() {
        if (isEmpty()){
            throw new IllegalStateException();
        }
        return elements[(front+1) % maxSize];
    }

    @Override
    public int size() {
        if(this.front<=rear){
            return rear-front;
        }
        return rear+maxSize-front;

    }

    @Override
    public void clear() {
        this.front = 0;
        this.rear = 0;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    private boolean isFull(){
        return (rear+1) % maxSize == front;
    }
}

 

2. 시간복잡도

자료구조	접근	탐색	삽입	삭제	비고
큐	O(n)	O(n)	O(1)	O(1)	링크를 타고 순회

1) 접근

 큐의 맨 뒤에 데이터에 접근하려고 할 경우 모든 데이터를 순회해야하므로 시간복잡도는 O(n).

 

2) 탐색

 찾으려는 데이터가 큐의 맨 뒤에 있을 경우, 모든 데이터를 순회해야하므로 시간 복잡도는 O(n).

 

3) 삽입, 삭제

 큐 맨 뒤에 데이터를 삽입하거나 맨 앞의 데이터를 삭제할 때에는 바로 삭제만 하면 되므로 시간복잡도는 O(1). 그러나 특정 데이터를 삭제하려고 하거나 특정 데이터 앞이나 뒤에 데이터를 넣으려고 한다면, 탐색을 해야 하기 때문에 최대 O(n)의 시간 복잡도가 발생한다.

 

정리

  큐는 FIFO(First In First Out) 구조이며, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대개념이다. CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시, 메시지큐 등에 사용된다.

 

 

참조

면접을 위한 CS 전공지식 노트

야놀자 테크스쿨 패스트캠퍼스 온라인 강의 - 자료구조/알고리즘