큐(Queue) - Array와 LinkedList로 구현, 원형큐, 덱/데크(Deque)

큐란?

큐는 FIFO(First In First Out) 원칙을 따르는 선형 데이터 구조이다. 즉, 삽입된 순서대로 삭제가 처리된다.

 

 

 

큐 연산

 

주요 연산인 enqueue, dequeue 외에도 peek(front), empty, size 등의 연산이 있다.

1. enqueue: 큐의 뒤(rear) 끝에 새로운 데이터를 추가하는 연산
2. dequeue: 큐의 앞(front) 끝에서 데이터를 제거하고 반환하는 연산
3. front 또는 peek: 큐의 앞에 있는 데이터를 제거하지 않고 반환하는 연산
4. empty: 큐가 비어 있는지 확인하는 연산
5. size: 큐에 있는 데이터의 개수를 반환하는 연산

 

 

 

큐 구현

큐도 스택과 마찬가지로 배열이나 연결 리스트를 사용하여 구현할 수 있다.

데이터 크기 예측 가능한 경우         ->   배열
메모리 사용이 제한된 환경             ->   배열
데이터 크기 미리 예측 불가/가변적 ->   연결리스트

 

 

배열을 사용한 구현

인덱스를 통해 빠르게 요소에 접근 가능

고정된 크기의 배열을 사용.

큐가 가득 차면 더이상 데이터를 추가할 수 없다는 제한이 있음.

class ArrayQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] queueArray;
    private int nItems;

    public ArrayQueue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % maxSize;
        queueArray[rear] = value;
        nItems++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int temp = queueArray[front];
        front = (front + 1) % maxSize;
        nItems--;
        return temp;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queueArray[front];
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public boolean isFull() {
        return (nItems == maxSize);
    }

    public int size() {
        return nItems;
    }
}

 

 

 

연결리스트를 사용한 구현

• 연결리시트는 필요에 따라 크기를 동적으로 조절할 수 있다.
• 필요한 만큼 메모리를 할당하므로, 배열에서 발생할 수 있는 미사용 공간의 낭비가 없다.
• 각 요소가 다른 메모리 위치에 저장되므로, 배열보다 접근시간이 느릴 수 있다.
• pop과 push  연산에 별도의 포인터가 필요하다

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedListQueue {
    private ListNode front;
    private ListNode rear;
    private int nItems;

    public LinkedListQueue() {
        front = null;
        rear = null;
        nItems = 0;
    }

    public void enqueue(int value) {
        ListNode newNode = new ListNode(value);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        nItems++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int temp = front.value;
        front = front.next;
        nItems--;
        if (isEmpty()) {
            rear = null;
        }
        return temp;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.value;
    }

    public boolean isEmpty() {
        return (front == null);
    }

    public int size() {
        return nItems;
    }
}

 

 

 

 

큐의 활용

• 프로세스 스케줄링
• 인쇄 대기열
• 데이터 패킷 관리 : 네트워크 라우터와 스위치는 들어오는 패킷을 큐에 저장하고 순서대로 처리
• BFS (너비 우선 탐색)

 

 

 

---

 

 

 

원형큐란?

 

배열을 사용한 구현에서 언급했다시피, 기존 큐는 공간이 꽉 차게 되면 더이상 요소를 추가할 수 없었다. 심지어 전부 dequeue되어 충분히 공간이 남게 되어도 앞쪽으로는 요소를 추가할 수 없었따.

이는 원형큐를 이용하여 보완할 수 있다. 그림과 같이 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조이다.

 

원형큐의 동작을 살펴보자.

그림과 같이 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작 점과 끝점을 따라 투포인터가 움직인다.

enqueue 시 rear 포인터가 앞으로 이동

dequque 시 front 포인터가 앞으로 이동

만약 rear포인터가 front 포인터 자리까지 도달했다면, 공간이 부족하다는 뜻이다.

❗️그냥 구현하면 원소가 없을때와 완전히 꽉 찼을 때 구분할 수 없다.
이를 구별하기 위해
1. 원소를 실제 공간보다 한칸 적게 채우는 방법
2. 따로 비어있는지 여부를 플래그를 붙이는 방법

 

 

배열을 사용하여 구현하기

class CircularQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] queueArray;
    private int nItems;

    public CircularQueue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % maxSize;
        queueArray[rear] = value;
        nItems++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int temp = queueArray[front];
        front = (front + 1) % maxSize;
        nItems--;
        return temp;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queueArray[front];
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public boolean isFull() {
        return (nItems == maxSize);
    }

    public int size() {
        return nItems;
    }
}

 

 

 

 

---

 

 

 

덱/데크(Deque)란?

 

덱(Double-ended Queue)이란 큐의 일반화된 형태로, 양쪽 끝에서 삽입/삭제가 모두 가능한 자료구조이다.

즉, 큐와 스택의 혼합 방식이다.

 

 

덱 연산

 

• AddFirst: 덱의 앞쪽에 요소를 추가
• AddLast: 덱의 뒤쪽에 요소를 추가
• RemoveFirst: 덱의 앞쪽에서 요소를 제거하고 반환
• RemoveLast: 덱의 뒤쪽에서 요소를 제거하고 반환

 

덱 구현

 

배열, 연결리스트로 모두 구현 가능하지만 그림과 같이 이중 연결 리스트로 구현하는 편이 보편적이다.

투포인터 방식으로, 양쪽에 head와 tail이라는 두개의 포인터가 있다.

새로운 아이템이 추가될 때 마다 앞/뒤로 연결시켜주고, 포인터를 이동시키면 된다.

 

(이중)연결리스트를 사용한 구현

 

class Deque {
    private LinkedList<Integer> deque;

    public Deque() {
        deque = new LinkedList<>();
    }

    public void addFirst(int value) {
        deque.addFirst(value);
    }

    public void addLast(int value) {
        deque.addLast(value);
    }

    public int removeFirst() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        return deque.removeFirst();
    }

    public int removeLast() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        return deque.removeLast();
    }

    public int peekFirst() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        return deque.peekFirst();
    }

    public int peekLast() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        return deque.peekLast();
    }

    public boolean isEmpty() {
        return deque.isEmpty();
    }

    public int size() {
        return deque.size();
    }
}