Queue와 Deque(큐와 덱)

도입

기본 자료구조인 Queue와 Dequeue에 대하여 알아보자.

 

---

Queue

• Queue는 선입 선출의 자료구조이다.
• 데이터를 넣는 부분과 빼는 부분이 다르다.
• push(x) : 데이터를 넣는 연산
• pop(x) : 데이터를 빼는 연산

C++은 STL의 queue를 Python은 collections의 deque를 사용하면 된다. 

자바를 사용하는 경우 java.util.Queue의 Queue를 사용하면 된다.

 

삽입과 삭제

Queue에 20을 삽입한 경우

Queue에서 삽입을 한 경우이다. Queue의 뒷 부분에 20이 삽입되는 것을 알 수 있다.

 

Queue에 pop을 한 경우

Queue에서 pop을 수행한 경우는 앞 부분에 43가 나오는 것을 알 수 있다.

위 삽입과 삭제 과정에서 주목해야할 점은 데이터가 들어가는 방향과 나오는 방향이 다르다는 점이다.(Queue의 가장 큰 특징)

 

구현의 주의점

Queue를 구현하는 방법은 데이터를 삽입하는 부분과 나오는 부분에 대한 포인터를 두어 사용할 수 있다. 

큐를 구현하면 삽입과 삭제를 $O(1)$로 구현할 수 있다. 하지만, 이를 잘못 구현하면 $O(n)$의 복잡도가 나올 수도 있다.

삭제를 $O(n)$으로 구현한 예

위의 그림이 잘못 구현한 예이다. 위 처럼 삭제 시 모두 데이터를 옮길 경우 $O(n)$이라는 시간 복잡도를 보여주게 된다.

pop을 구현할 때 위와 같은 실수를 하지 않기 위해서는 삭제를 하는 포인터만 옆으로 옮겨주기만 하면 된다. 하지만 이 방법은 LinkedList로 구현을 할 경우에는  문제가 되지 않지만, ArrayList로 구현할 경우에는 문제가 된다.

 

배열의 크기가 10000로 단순 Queue를 구현해서 배포했다고 가정하자. 사람들이 열심히 삽입과 삭제를 통해 Queue를 사용하고 있다. 어느 날 분명 size는 100이 안넘는데 데이터를 삽입하지 못하는 문제점이 발생한다. 이유가 무엇일까? 단순히 Point를 옮기는 방법으로 구현을 하면 계속해서 포인터 값이 올라간다는 문제가 발생한다.

삭제시 포인트의 이동

위 예시를 보면 삭제를 진행할 때 삭제 Point가 0에서 1로 증가한다. 삽입의 포인터는 삽입을 할 경우 계속 증가하는 것을 알 수 있다.

따라서, 위의 방법대로만 구현을 할 경우에는 계속 사용시에 앞 부분의 메모리를 사용하지 못한다는 문제점이 발생하게 된다.

이를 해결하기 위해서는 $%$ 연산자를 활용하여 환형으로 큐를 구현하여주면 된다. 즉 $size$가 $10000$이라고 하면, $9999$의 다음을 $0$으로 만들어주기 위해 $%10000$을 한 결과로 만들어주면 되는 것이다.

 

아래는 Queue를 기본으로 구현해본 것이다.

    /**
    * 10000번의 삽입만 가능한 기본 Queue
    * push(x) : 삽입
    * pop() : 삭제
    * size() : 크기
    * isEmpty() : 비어있는지?
    * front() : 앞 부분
    * back() : 뒷 부분
    */
    class Queue {
        private int list[] = new int[10000];
        private int front = 0;
        private int back = 0;

        public boolean push(int X) {
            list[front++] = X;
            return true;
        }

        public int pop() {
            if(isEmpty())
                return -1;
            return list[back++];
        }

        public int size() {
            return front - back;
        }

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

        public int front() {
            if (isEmpty())
                return -1;
            return list[back];
        }

        public int back() {
            if (isEmpty())
                return -1;
            return list[front - 1];
        }
    }

 

Deque

• Deque은 양 끝에서 삽입과 삭제를 모두 할 수 있는 자료구조로 큐의 응용이다.
• 삽입과 삭제를 해줄 곳을 지정하여 구현하는 것이다.
• 삽입과 삭제를 하는 부분을 동일한 위치로만 사용하면 Stack이 된다. 

덱 구현을 위해서 환형 Queue를 사용하였다.

 

 

    static class Deque{
        int[] list = new int[10000];
        int listSize = 10000;
        int front = 0;
        int back = 0;

        public boolean isEmpty(){
            return front == back;
        }
        public void pushFront(int X){
            list[(front++ + listSize)%listSize] = X;
        }

        public void pushBack(int X){
            list[(--back+listSize)%listSize] = X;
        }

        public int popFront(){
            if(isEmpty())
                return -1;
            return list[(--front+listSize)%listSize];
        }

        public int popBack(){
            if(isEmpty())
                return -1;
            return list[(back++ + listSize)%listSize];
        }

        public int size(){
            return front - back;
        }

        public int front(){
            if(isEmpty())
                return -1;
            return list[(front - 1 + listSize)%listSize];
        }

        public int back(){
            if(isEmpty())
                return -1;
            return list[(back + listSize)%listSize];
        }
    }

---

배운내용

자료구조 Queue와 Queue의 응용인 Deque를 알아보았다.

Queue를 구현할 때 유의점에 대하여 알아보았고, 해결하기 위한 방안을 알아보았다.

Deque에서 한 부분으로만 삽입과 삭제를 진행하면 Stack이 된다.

 

잘못된 정보가 있을 경우 댓글 부탁드립니다. :)