# 파이썬으로 구현한 자료구조 - 큐

- Author: @baealex
- Published: 2019-09-03
- Updated: 2020-02-17
- Source: http://blex.me/@baealex/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%9C-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90
- Tags: 프로그래밍, 파이썬, 자료구조

---

## 큐(Queue)

> 은행에서는 먼저 기다린 손님을 우선으로 일을 처리해 줍니다. 이처럼 삽입 순서와 삭제 순서가 일치하도록 하는 자료구조를 큐라고 합니다.

앞서 익혔던 스택의 경우에는 늦게 들어온게 가장 먼저 나가는 방식인 LIFO 였으나 큐의 경우에는 스택과 다르게 선입선출, FIFO(First In First Out) 방식을 사용한다. 우리의 법치국가 사회에서 가장 많이 볼 수 있는 자료구조다. 큐의 구현 방식은 아래와 같다.

- 순차 큐
- 원형 큐
- 연결 큐

**순차 큐** : 순차 큐는 배열(순차 자료구조)로 구현하는 것이 일반적이다. 큐의 경우에는 들어오는 방향인 `rear`와 나가는 방향인 `front`가 존재하는데 순차 큐는 `rear`와 `front`가 인덱스 번호로 저장된다. 요소가 추가되거나 삭제될 때 `rear`와 `front`의 값을 변경하며 저장한다.

**원형 큐** : 만일 순차 큐에서 `rear`가 마지막 인덱스에 위치하면 어떻게 되는걸까? 안타깝게도 순차 큐의 생명은 끝난다. 만일 `front`가 있는 위치가 아니라면 `rear`를 다시 앞으로 보낼 수 있지 않을까? 그게 원형 큐다. 원형 큐는 순차 큐와 마찬가지로 순차 자료구조를 활용하여 만들기 때문에 물리적으로 연결된 구조가 아니지만 논리적으로 연결되어 있다고 가정하고 구현한다.

**연결 큐** : 위 두가지 큐 구조의 단점은 순차 자료구조인 관계로 역시 크기를 변경하기 어렵다는데 있다. 연결 큐는 연결 리스트를 활용하여 구현하는 큐로 크기에 제한없이 사용할 수 있다는 장점이 있다.

이 글에서는 연결 큐와 데크만 구현한다.

<br>

#### 연결 큐

연결 큐에서 구현해야 할 메서드는 아래와 같다.

- 연결 큐의 공백 상태 검사
- 연결 큐의 원소 삽입
- 연결 큐의 원소 삭제
- ~~연결 큐의 원소 검색~~

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.link = None
    
    def __str__(self):
        return str(self.data)

class Queue:
    def __init__(self, data):
        new_node = Node(data)
        self.front = new_node
        self.rear = new_node
        self.front.link = self.rear
```

큐는 아까 언급했듯 값이 들어오는 `rear`와 빠져나가는 `front`가 존재한다. 단순 연결 리스트로 구현하며 `front`에서 `rear`로 링크를 연결하였다.

**연결 큐의 공백 상태 검사**

```python
def isEmpty(self):
    if self.front == self.rear:
        return True
    else:
        return False
```

둘다 `None`인 상태를 검사하는게 가장 이상적인 형태겠지만 `if`문을 조금이라도 줄이기 위해서 하나인 상태에서는 삭제를 불가하게 하기위해 `front`가 `rear`인 경우에는 비어있다고 반환한다.

**연결 큐의 원소 삽입**

```python
def enQueue(self, data):
    new_node = Node(data)
    self.rear.link = new_node
    self.rear = new_node
```

큐의 삽입은 `enQueue`라고 부른다. 삽입이 되었을 경우 `rear`의 링크는 새로운 노드에 붙이고 `rear`는 새로운 노드로 변경하였다.

**연결 큐의 원소 삭제**

```python
def deQueue(self):
    if not self.isEmpty():
        node = self.front
        value = node.data
        self.front = self.front.link
        del node
        return value
```

프론트의 값을 추출하고 프론트를 다음으로 옮기며 기존 프론트는 삭제하였다. 다만 위에서 언급했듯 `front`가 `rear`인 경우 값을 추출할 수 없으므로 삭제없이 값을 출력하는 `peek` 메서드를 추가했다.

```python
def peek(self):
    return self.front.data
```

<br>

##### 연결 큐 전체 소스코드

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.link = None
    
    def __str__(self):
        return str(self.data)

class Queue:
    def __init__(self, data):
        new_node = Node(data)
        self.front = new_node
        self.rear = new_node
        self.front.link = self.rear

    def __str__(self):
        print_queue = '<= [ '
        node = self.front
        while True:
            print_queue += str(node)
            if(node == self.rear):
                break
            try:
                node = node.link
            except:
                break
            print_queue += ', '
        print_queue += ' ] <='
        return print_queue

    def isEmpty(self):
        if self.front == self.rear:
            return True
        else:
            return False

    def enQueue(self, data):
        new_node = Node(data)
        self.rear.link = new_node
        self.rear = new_node

    def deQueue(self):
        if not self.isEmpty():
            node = self.front
            value = node.data
            self.front = self.front.link
            del node
            return value

    def peek(self):
        return self.front.data
        

if __name__=="__main__":
    m_queue = Queue(5)
    print(m_queue)
    m_queue.enQueue(7)
    print(m_queue)
    m_queue.enQueue(9)
    print(m_queue)
    print('deQueue :', m_queue.deQueue())
    print('deQueue :', m_queue.deQueue())
    print('deQueue :', m_queue.deQueue())
    print('   peek :', m_queue.peek())
    for i in range(10):
        m_queue.enQueue(i)
    print(m_queue)
    print('deQueue :', m_queue.deQueue())
```

```
<= [ 5 ] <=
<= [ 5, 7 ] <=
<= [ 5, 7, 9 ] <=
deQueue : 5
deQueue : 7
deQueue : None
   peek : 9
<= [ 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] <=
deQueue : 9
```

<br>

#### 데크(Deque)

데큐? 디큐? 데크? 디크? 덱? 무엇이 올바른 발음인지 모르지만 디큐의 경우에는 큐에서 요소를 삭제하는 `deQueue`와 곂치므로 아니지 않을까... 여하지간 데크와 큐의 차이점은 큐는 `rear`로 들어와서 `front`로 나가는 방식을 가졌으나 데크는 `rear`로 들어오거나 나갈 수 있고, `front`에서도 들어오거나 나갈 수 있다.

```
deQueueFromFront <=> enQueueFromFront [ Deque ] enQueueFromRear <=> deQueueFromRear
```

위와 같은 형태로 구성되었다. 따라서 큐의 경우에는 한방향으로 들어오고 나가므로 단순 연결 리스트를 사용했으나 데크의 경우는 이중 연결 리스트를 사용하여 구현하는 것이 이상적이다.

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.llink = None
        self.rlink = None

    def __str__(self):
        return str(self.data)

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
```

위처럼 `Deque`의 구조 자체는 `Queue`와 동일하지만 노드의 형태가 다르다. 데크의 구현되어야 할 메서드는 아래와 같다.

- 데크의 공백 상태 검사
- 데크의 앞단에서 원소 삽입
- 데크의 뒷단에서 원소 삽입
- 데크의 앞단에서 원소 삭제
- 데크의 뒷단에서 원소 삭제
- ~~연결 큐의 원소 검색~~

**데크의 공백 상태 검사**

```python
def isEmpty(self):
    if self.front == self.rear:
        return True
    else:
        return False
```

공백 상태 검사는 큐와 동일하게 하였다. 같은 곳을 가리키면 비어있는 상태로 간주한다.

**데크의 원소 삽입**

```python
def insertFront(self, data):
    new_node = Node(data)       # 새노드 생성
    self.front.llink = new_node # 기존 프론트의 왼쪽 링크를 새노드로 변경
    new_node.rlink = self.front # 새노드의 오른쪽 링크를 기존 프론트로 변경
    self.front = new_node       # 프론트를 새노드로 변경

def insertRear(self, data):
    new_node = Node(data)       # 새노드 생성
    self.rear.rlink = new_node  # 기존 레어의 오른쪽 링크를 새노드로 변경
    new_node.llink = self.rear  # 새노드의 왼쪽 링크를 기존 레어로 변경
    self.rear = new_node        # 레어를 새노드로 변경
```

**데크의 원소 삭제**

```python
def deleteFront(self):
    if self.isEmpty():
        return
    node = self.front
    value = node.data
    self.front = self.front.rlink # 기존 프론트를 프론트의 오른쪽으로 변경
    del node                      # 기존 프론트 삭제
    return value

def deleteRear(self):
    if self.isEmpty():
        return
    node = self.rear
    value = node.data
    self.rear = self.rear.llink   # 기존 레어를 레어의 왼쪽으로 변경
    del node                      # 기존 레어 삭제
    return value
```

<br>

##### 데크 전체 소스코드

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.llink = None
        self.rlink = None

    def __str__(self):
        return str(self.data)

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None

    def __str__(self):
        node = self.front
        print_deque = ' <=> [ '
        while True:
            print_deque += str(node)
            if node == self.rear:
                break
            try: node = node.rlink
            except: break
            print_deque += ', '
        print_deque += ' ] <=>'
        return print_deque

    def insertFront(self, data):
        new_node = Node(data)
        if self.front == None and self.rear == None:
            self.front = new_node
            self.front.rlink = self.rear
            self.rear = new_node
            self.rear.llink = self.front
        else:
            self.front.llink = new_node
            new_node.rlink = self.front
            self.front = new_node

    def insertRear(self, data):
        new_node = Node(data)
        if self.rear == None and self.front == None:
            self.rear = new_node
            self.rear.llink = self.front
            self.front = new_node
            self.front.rlink = self.rear
        else:
            self.rear.rlink = new_node
            new_node.llink = self.rear
            self.rear = new_node

    def deleteFront(self):
        if self.isEmpty():
            return
        node = self.front
        value = node.data
        self.front = self.front.rlink
        del node
        return value

    def deleteRear(self):
        if self.isEmpty():
            return
        node = self.rear
        value = node.data
        self.rear = self.rear.llink
        del node
        return value


    def peekFront(self):
        return self.front.data

    def peekRear(self):
        return self.front.data

    def isEmpty(self):
        if self.front == self.rear:
            return True
        else:
            return False

if __name__ == "__main__":
    m_deque = Deque()
    m_deque.insertFront(5)
    m_deque.insertFront(4)
    m_deque.insertFront(3)
    print(m_deque)
    m_deque.insertRear(10)
    m_deque.insertRear(9)
    m_deque.insertRear(10000)
    print(m_deque)
    print('Delete Front :', m_deque.deleteFront())
    for i in range(5):
        print('Delete Rear :', m_deque.deleteRear())
    print('Peek Rear   :', m_deque.peekRear())
    print(m_deque)
```

```
 <=> [ 3, 4, 5 ] <=>
 <=> [ 3, 4, 5, 10, 9, 10000 ] <=>
Delete Front : 3
Delete Rear : 10000
Delete Rear : 9
Delete Rear : 10
Delete Rear : 5
Delete Rear : None
Peek Rear   : 4
 <=> [ 4 ] <=>
```

결과를 살펴보면 재미난 사실을 알 수 있다. 데이터의 삽입을 `5 > 4 > 3`으로 진행하여 `5`가 가장 먼저 나가야 할 요소인데 레어쪽으로 `10 > 9 > 10000`이 들어오면서 사이에 가둬지고 말았다. 레어쪽으로 들어왔던 `10`도 마찬가지다. `fornt`만 잘 살펴보면 나중에 들어온 `3`이 가장 먼저 나갔다는 사실을 알 수 있다.

큐에선 `rear`에 들어와서 `front`로 나왔지만 데크에선 양쪽에서 삽입삭제가 가능하므로 `insertRear`, `deleteRear`만 사용하는 경우 스택처럼 사용될 수 있다. `front`에서만 삽입삭제 하는 경우도 똑같다. `insertRear`와 `deleteFront` 또는 그 반대로 사용하는 경우 기존 큐와 똑같은 작업이 가능하다.