[자료구조] queue 구현

작성일 | In |

Queue와 그 성질에 대해 알아보고, 직접 구현해보자

Queue

큐는 먼저 들어온 데이터가 먼저 나가는 First In First Out 구조를 가진 자료구조이다. 파이프 뒤쪽으로는 데이터를 계속 집어넣고, 앞쪽으로는 데이터를 계속 꺼낸다고 보면 되겠다.

queue

가장 먼저 줄을 선 사람이 가장 먼저 용무를 끝내고 사라지듯, 큐도 그러하다.


구현

Class

일단 꺼내는 것은 맨 처음, 추가하는 것은 맨 뒤이기 때문에 이를 알고 있어야 한다.

1
2
3
4
5
class Queue:
    def __init__(self):
        self.first = None
        self.last = None
        self.length = 0

데이터를 가지고 있는 Node도 만들어야 한다.

1
2
3
4
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Node는 본인의 data와 다음 Node를 알고 있다.

Queue add

큐에 데이터를 추가한다. 비어있는 큐라면 self.first에 data를 추가하고, 그렇지 않으면 Queue.last의 next에 data를 추가한다.

1
2
3
4
5
6
7
8
9
    def add(self, data):
        new_item = Node(data)
        if not self.first: # 비어있는 Queue라면
            self.first = new_item
            self.last = self.first
        else: # 비어있는 Queue는 아님.
            self.last.next = new_item
            self.last = self.last.next
        self.length += 1

Queue pop

큐에서 데이터를 꺼내온다. 비어있는 경우에 예외처리를 한다.

1
2
3
4
5
6
7
8
9
10
11
    def pop(self):
        if not self.first:
            raise ValueError

        data = self.first # 꺼내올것은 가장 첫번째 Node
        self.first = self.first.next # 첫번째 Node가 사라지면 이제 첫번째 Node는 first.next가 된다. 

        if not self.first: # queue가 비게 되면
            self.last = None # last도 없앤다.
        self.length -= 1
        return data.data

Queue get

가장 첫번째 데이터를 return한다.

1
2
3
4
    def get(self):
        if not self.first:
            raise ValueError
        return self.first.data

Queue traverse

queue를 순회하면 가지고 있는 데이터를 보여준다.

1
2
3
4
5
6
7
    def traverse(self):
        arr = []
        start = self.first
        while start:
            arr.append(start.data)
            start = start.next
        return arr


실행

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
q = Queue()
q.add(1)
q.add(3)
q.add(2)
print("queue 순회 : {}".format(q.traverse()))
print("queue 첫번째 : {}".format(q.get()))
print("queue에서 원소 빼기 : {}".format(q.pop()))
print("queue에서 원소 빼기 : {}".format(q.pop()))
print("queue에서 원소 빼기 : {}".format(q.pop()))
print("queue에서 원소 2개 뺀 후 : ", q.traverse())

'''
queue 순회 : [1, 3, 2]
queue 첫번째 : 1
queue에서 원소 빼기 : 1
queue에서 원소 빼기 : 3
queue에서 원소 빼기 : 2
queue에서 원소 2개 뺀 후 :  []

'''