[자료구조] 큐 / 원형 큐 / 양방향 큐

선형 큐(Queue)

컴퓨터의 기본 선형 자료구조 중 하나로 FIFO(First In First Out), 선입선출의 특징을 갖는다.

기본적으로 데이터 추가(Enqueue), 꺼내기(Dequeue), 큐 공간 확인 동작으로 이루어진다. 한쪽 끝을 front, 반대쪽 끝을 rear라고 할 때, rear로 데이터가 추가되고, front에서 데이터가 꺼내진다.

 

큐 오버플로우(Overflow), 언더플로우(Underflow)

오버플로우 - 큐 크기만큼 데이터가 꽉 차서 더이상 들어가지 않을 때

언더플로우 - 큐가 비어있는데 데이터를 꺼내려고 하는 경우

 

큐 사용처

입력 순서대로 데이터 처리가 필요할 때 사용한다.

• 프린트 출력 대기열
• 그래프 너비우선탐색(BFS - Breath First Search)

 시간복잡도 ( Big O )

• 삽입(Insertion) - O(1)
• 삭제(Deletion) - O(1)(dequeue) / O(N)(remove)
• 검색(Search) - O(N)

큐의 삽입은 front에서만 일어나고 삭제는 항상 rear에서만 일어나므로 삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정이다.

선형 큐(Java)

자바에서는 JDK 1.5부터 java.util.Queue;에 만들어진 큐 자료구조가 존재하지만 인터페이스이기 때문에

Queue queue= new Queue(); 같이 만들면 메소드를 전부 오버라이딩 해줘야한다.

그래서 Queue queue = new LinkedList();같이 만든다.

LinkedList에 Queue에 필요한 연산이 다 있다. 뻗어나온 애를 상속받아 만든 것이기 때문에 다형성을 이용해 할당해서 사용하는 것이다.

 

주로 사용하는 메소드

Queue queue = new LinkedList();로 만들었다고 가정한다.

메소드 이름	사용 예시	설명
add	queue.add(1);	큐에 데이터를 넣는다. 제네릭으로 타입에 제한을 두지 않는다면 어떤 타입이든 들어갈 수 있다. Enqueue의 기능을 한다.
poll	queue.poll();	큐에서 front 데이터를 빼는 함수, 가장 처음에 들어간 데이터를 뺀다. 데이터가 더이상 없는데 poll을 해주면 아무일도 일어나지 않는다.  null을 반환한다.
peek	queue.peek();	pop()과 같은 front 데이터를 가져오는 함수. poll()은 뽑은 데이터가 사라지지만 peek()는 사라지지 않는다. 데이터가 더이상 없는데 peek을 해주면 아무일도 일어나지 않는다. null을 반환한다.
contains	queue.contains(1);	contains 내부의 값이 큐 내부에 있는지 확인하는 함수. boolean 타입으로 반환한다.
size	queue.size();	현재 큐의 크기를 반환한다.
isEmpty	queue.isEmpty();	빈 큐라면 true, 아니면 false를 반환한다.
clear	queue.clear();	빈 큐로 만들어주는 함수.

사용 예시

 

    public static void main(String[] args) {
        Queue queue1 = new LinkedList();
        Queue<Integer> queue2 = new LinkedList(); // 정수형 stack
        Queue<? super Number> queue3 = new LinkedList(); // 숫자만 받는 stack
        String[] arr = {"Hi", "Im", "Ian"};

        System.out.println(queue1.poll());   // null
        System.out.println(queue1.peek());   // null

        queue1.add(1);
        queue1.add(3.14);
        queue1.add('a');
        queue1.add("문자열");
        queue1.add(arr);
        queue1.add(5);

        System.out.println(queue1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586, 5]
        System.out.println(queue1.poll());   // 1
        System.out.println(queue1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586]
        System.out.println(queue1.peek());  // 3.14
        System.out.println(queue1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586]
        System.out.println(queue1.size());  // 5
        System.out.println(queue1.isEmpty()); // false
        queue1.clear();
        System.out.println(queue1.isEmpty()); // true

        queue2.add(1);
        queue2.add(3.14);  //에러
        queue2.add('a');   //에러
        queue2.add("문자열");//에러
        queue2.add(arr);       //에러

        queue3.add(1);
        queue3.add(3.14);
        queue3.add('a');   //에러
        queue3.add("문자열");//에러
        queue3.add(arr);       //에러
    }

위 큐를 사용할 수 없는 경우, 직접 큐 구현해야 한다.

 

ArrayList를 이용한 선형 큐 구현

 

import java.util.ArrayList;

class MyQueue {
    ArrayList list;

    MyQueue() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if(this.list.size()==0) return true;
        return false;
    }

    public void push(int data) {
        this.list.add(data);
    }

    public Integer pop() {
        if(this.isEmpty()){
            System.out.println("Queue is empty");
            return null;
        }
        int data=(int)this.list.get(0);
        this.list.remove(0);
        return data;
    }

    public Integer peek() {
        if(this.isEmpty()){
            System.out.println("Queue is empty");
            return null;
        }
        return (int)this.list.get(0);
    }
}

ArrayList를 이용하여 만들면 크기(size)가 유기적이다.

 

** 배열로 구현했을 경우, rear가 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없다.(가능은 하지만 낭비가 심하다) 그래서 배열로는 원형 큐를 구현한다. 원형 큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.

선형 큐(Python)

리스트를 이용한 선형 큐 사용

 

queue = []

queue.append(0)
queue.append(1)
queue.append(2)

del queue[0]   # 요소 0 제거
queue.pop(0)   # 요소 1 제거

 

append를 통해 enqueue, del 혹은 pop을 통해 dequeue를 한다.

하지만 pop이나 del은 시간복잡도가 O(N)이기 때문에 그닥 사용을 추천하지는 않는다. 

 

queue 라이브러리를 이용

 

from queue import Queue
que = Queue()
que.put(1)
que.put(2)
que.put(3)

print(que.get())

deque와 같은 성능을 보이지만 list나 deque와 달리 인덱스로 데이터 접근하는 것을 기본적으로는 지원하지 않는다.

그래서 보통 deque를 쓰지 Queue를 쓰지는 않는다.

 

원형 큐(Circular Queue = Ring Buffer)

선형 큐의 문제점을 보완하기 위한 자료구조이다. 

Circular Queues in Data Structure

Enqueue

rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다.

배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둔다. (rear+1)%arraysize == front 라면 배열이 포화상태인걸로 판단하여 데이터 삽입이 이루어지지 않게 된다.

 

Dequeue

front의 포인터를 1증가 시키고 그 위치의 데이터를 배열에서 가지고 온다. rear==front 조건이라면 배열이 공백상태인걸로 판단하여 Dequeue가 실행되지 않는다.

 

원형 큐(Java)

배열을 이용한 원형 큐 구현

 

class MyQueue {
    int[] arr;
    int front = 0;
    int rear = 0;

    MyQueue(int size) {
        arr = new int[size + 1];
    } // 하나는 포화상태 확인용이기에 size만큼 데이터를 담으려면 size+1해줘야함
    public boolean isEmpty() {
        return this.rear == this.front;
    }
    public boolean isFull() {
        return (this.rear + 1) % this.arr.length == this.front;
    }
    public void enqueue(int data) {
        if (this.isFull()) {
            System.out.println("Queue is full!");
            return;
        }

        this.rear = (this.rear + 1) % this.arr.length;
        this.arr[this.rear] = data;
    }

    public Integer dequeue() {
        if (this.isEmpty()) {
            System.out.println("Queue is empty!");
            return null;
        }

        front = (front + 1) % this.arr.length;
        return this.arr[front];
    }
}

 

양방향 큐(Deque = 덱 = Double-ended queue)

말그대로 큐의 양끝이 front이면서 rear인 형태의 자료구조이다. 큐처럼 한쪽에서만 데이터가 들어오고 한쪽으로만 데이터가 나가는 것이 아닌 양쪽 끝에서 데이터의 삭제와 삽입 모두 가능한 것이다. 이러한 특성 때문에 데이터가 삽입과 삭제의 자유도가 높다. 즉, 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다는 것이다. 일부 기능을 제한하여 용도에 맞게 변형이 가능하다.

일부 기능을 제한한 데크에는 2가지 종류가 있다.

어느 한 쪽의 입력을 제한한 데크를 스크롤(Scroll)이라고 한다.

어느 한 쪽의 출력을 제한한 데크를 Shelf 라고 한다.

선입선출의 방식으로 이해하려 하면 이해가 힘들 수 있으니 아예 다른 거라고 생각하고 접근하는 편이 좋다.

그러나 실제로 양쪽에서 삽입과 삭제가 필요한 경우는 많지 않고 큐나 스택을 구현한 후 추가적으로 삽입, 삭제가 필요한 경우 사용한다. 보통은 스케줄링에 많이 사용하며, 스케줄링이 복잡할 수록 큐와 스택보다 더 나은 효율을 보여주곤 한다.

 시간복잡도 ( Big O )

• 삽입(Insertion) - O(1)
• 삭제(Deletion) - O(1)(pop) / O(N)(remove)
• 검색(Search) - O(N)

양방향 큐(Java)

자바에서 JDK 1.6부터 있는 Deque는 인터페이스이다.( + ArrayDeque ) Queue 인터페이스를 상속받아 만들어졌다.

Deque<Integer> stack = new ArrayDeque<Integer>(); 이런식으로 사용한다.

이미 구현되어있는 List 구조에서 Queue에서 원하는 선입선출기능, Deque에서 원하는 Queue의 확장기능을 추가만 하면 되는 것이기 때문에 구현량은 생각보다 빈약하다.

 

데이터를 넣는 것을 add(offer)라고 하고, 빼는 것을 remove(poll)라고 한다.

구현할때도 front 쪽을 addFirst같이 되어있고, rear 쪽을 addLast 이런식으로 되어있다.

add, remove는 더 이상 없거나, 더 이상 뺄 데이터가 없으면 예외를 발생시키지만, offer나 poll은 null이나 false의 리턴값을 반환한다. 그래서 리턴값을 받아서 처리할 수 있고, 저쪽은 예외처리를 해줘야한다. 어느걸 사용해도 무방하다.

 

자바에서 기본적으로 제공해주는 데크는 Deque deque=new ArrayDeque();라고 하면 된다.

deque.addFirst(3), deque.addLast(4), deque.removeFirst(), deque.removeLast()같이 사용한다.

 

ArrayList를 통한 데크구현은 간단하다. ArrayList의 get, remove, add, size를 이용하면 된다.

배열은 front와 end가 각각 front와 rear를 표현하게 만든다. front가 0이었는데 addFirst가 들어온다면 front가 뒤로 돌아서 arr.length-1이 되어야한다. 이부분을 잘 고려해서 만들어주면 된다.(나머지 연산 이용) 양방향 원형 데크가 만들어진다.

 

양방향 큐(Python)

collections 모듈에 deque을 사용하면 된다. 기본적인 스택, 큐 역할에 rotate같은 기능도 있기에 많이 쓰이는 듯 하다.

 

주요 함수:

• append() : deque의 right end에 요소 추가
• appendleft() :  deque의 lef end에 요소 추가
• pop() : deque의 right end의 요소 삭제
• popleft() : deque의 left end의 요소 삭제

사용 예시

 

from collections import deque
queue = deque([4,5,6])
queue.append(7)
print(queue)
queue.appendleft(8)
print(queue)
queue.popleft()
print(queue)
queue.popleft()
print(queue)
queue.pop()
print(queue)

 

아래는 우선순위 큐 포스팅 링크이다.

https://nukoori.tistory.com/50

[비선형 자료구조] 우선순위 큐(Priority Queue)