재밌다. 재밌다.

던져버리기

그만 재밌고 싶다…


큐(Queue)

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

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

  • 순차 큐
  • 원형 큐
  • 연결 큐

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

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

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

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


연결 큐

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

  • 연결 큐의 공백 상태 검사
  • 연결 큐의 원소 삽입
  • 연결 큐의 원소 삭제
  • 연결 큐의 원소 검색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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로 링크를 연결하였다.

연결 큐의 공백 상태 검사

1
2
3
4
5
def isEmpty(self):
    if self.front == self.rear:
        return True
    else:
        return False

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

연결 큐의 원소 삽입

1
2
3
4
def enQueue(self, data):
    new_node = Node(data)
    self.rear.link = new_node
    self.rear = new_node

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

연결 큐의 원소 삭제

1
2
3
4
5
6
7
def deQueue(self):
    if not self.isEmpty():
        node = self.front
        value = node.data
        self.front = self.front.link
        del node
        return value

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

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


연결 큐 전체 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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())
1
2
3
4
5
6
7
8
9
<= [ 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


데크(Deque)

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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와 동일하지만 노드의 형태가 다르다. 데크의 구현되어야 할 메서드는 아래와 같다.

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

데크의 공백 상태 검사

1
2
3
4
5
def isEmpty(self):
    if self.front == self.rear:
        return True
    else:
        return False

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

데크의 원소 삽입

1
2
3
4
5
6
7
8
9
10
11
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        # 레어를 새노드로 변경

데크의 원소 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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


데크 전체 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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)
1
2
3
4
5
6
7
8
9
10
 <=> [ 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에서만 삽입삭제 하는 경우도 똑같다. insertReardeleteFront 또는 그 반대로 사용하는 경우 기존 큐와 똑같은 작업이 가능하다.

WRITTEN BY

배진오

하고싶은 건 다 하면서 사는게 목표
im@baejino.com

comments powered by Disqus