[자료구조 및 알고리즘] Ch04. 큐(Queue)

큐 (Queue)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch04-01. 큐란

• 선입선출(First-In-First-Out이 보장되는 FIFO 구조)
• 순서가 보장된 처리
  • 사용자가 몰린 서버

Queue의 주요 동작으로는

• push(), offer(), add() : 데이터를 넣는 작업
• pop(), poll() : 데이터를 빼는 작업
• peek() : 데이터를 확인하는 작업

• 큐에 데이터가 입력되는 동작 : enqueue
• 큐에서 데이터가 빠지는 출력 동작 : dequeue

데이터가 들어갈 때는 제일 뒤(rear)쪽에다가 데이터가 들어가고, 데이터가 빠질 때는 가장 앞(front)쪽 부터 데이터가 빠지는 모양임.

Queue를 배열로 구현한다면?

배열로 큐를 구현할 경우에 앞에 있는 데이터가 빠질 때마다 데이터를 앞으로 한 칸씩 땡겨줘야 한다. 이럴 경우, N개의 데이터 만큼 앞으로 땡겨오게 되므로, 시간 복잡도가 $O(N)$ 까지 상승을 하게된다.

그렇기 때문에, 큐는 선형 구조이지만 배열 기반으로 구현해서 쓰는 것은 비효율적이라 하지 않는다.

Ch04-02. 선형 큐(Linear Queue)

Linked List(링크드 리스트)를 기반으로 해서 큐를 직접 구현

IQueue.java

package queue;

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

MyLinkedQueue.java

package queue;

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

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

    // 생성자
    public MyLinkedQueue() {
        this.size = 0;
        this.head = new Node(null); // dummy node
        this.tail = this.head;
    }

    // 큐에 데이터를 넣는 함수
    @Override
    public void offer(T data) {
        Node node = new Node(data);
        this.tail.next = node;
        this.tail = this.tail.next;
        this.size++;
    }
    // 큐에서 데이터를 빼오는 dequeue 연산을 하는 함수
    @Override
    public T poll() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        } // 큐가 비어있는 상태에서 데이터를 빼려고 하면 예외 발생하도록.
        Node node = this.head.next;
        this.head.next = node.next; // head를 가져올 데이터의 다음 데이터로 바꿈
        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; // head의 next는 가장 먼저 들어온 데이터를 갖고 있기 때문
    }

    @Override
    public int size() {
        return this.size;
    }

    // 처음 상태로 돌려주는 작업을 하는 함수
    @Override
    public void clear() {
        this.head.next = null;
        this.tail = head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
        // 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;
        }
    }
}

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

맨 위로 이동하기