큐(Queue)
은행에서는 먼저 기다린 손님을 우선으로 일을 처리해 줍니다. 이처럼 삽입 순서와 삭제 순서가 일치하도록 하는 자료구조를 큐라고 합니다.
앞서 익혔던 스택의 경우에는 늦게 들어온게 가장 먼저 나가는 방식인 LIFO 였으나 큐의 경우에는 스택과 다르게 선입선출, FIFO(First In First Out) 방식을 사용한다. 우리의 법치국가 사회에서 가장 많이 볼 수 있는 자료구조다. 큐의 구현 방식은 아래와 같다.
- 순차 큐
- 원형 큐
- 연결 큐
순차 큐 : 순차 큐는 배열(순차 자료구조)로 구현하는 것이 일반적이다. 큐의 경우에는 들어오는 방향인 rear와 나가는 방향인 front가 존재하는데 순차 큐는 rear와 front가 인덱스 번호로 저장된다. 요소가 추가되거나 삭제될 때 rear와 front의 값을 변경하며 저장한다.
원형 큐 : 만일 순차 큐에서 rear가 마지막 인덱스에 위치하면 어떻게 되는걸까? 안타깝게도 순차 큐의 생명은 끝난다. 만일 front가 있는 위치가 아니라면 rear를 다시 앞으로 보낼 수 있지 않을까? 그게 원형 큐다. 원형 큐는 순차 큐와 마찬가지로 순차 자료구조를 활용하여 만들기 때문에 물리적으로 연결된 구조가 아니지만 논리적으로 연결되어 있다고 가정하고 구현한다.
연결 큐 : 위 두가지 큐 구조의 단점은 순차 자료구조인 관계로 역시 크기를 변경하기 어렵다는데 있다. 연결 큐는 연결 리스트를 활용하여 구현하는 큐로 크기에 제한없이 사용할 수 있다는 장점이 있다.
이 글에서는 연결 큐와 데크만 구현한다.
연결 큐
연결 큐에서 구현해야 할 메서드는 아래와 같다.
- 연결 큐의 공백 상태 검사
- 연결 큐의 원소 삽입
- 연결 큐의 원소 삭제
연결 큐의 원소 검색
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로 링크를 연결하였다.
연결 큐의 공백 상태 검사
def isEmpty(self):
if self.front == self.rear:
return True
else:
return False둘다 None인 상태를 검사하는게 가장 이상적인 형태겠지만 if문을 조금이라도 줄이기 위해서 하나인 상태에서는 삭제를 불가하게 하기위해 front가 rear인 경우에는 비어있다고 반환한다.
연결 큐의 원소 삽입
def enQueue(self, data):
new_node = Node(data)
self.rear.link = new_node
self.rear = new_node큐의 삽입은 enQueue라고 부른다. 삽입이 되었을 경우 rear의 링크는 새로운 노드에 붙이고 rear는 새로운 노드로 변경하였다.
연결 큐의 원소 삭제
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 메서드를 추가했다.
def peek(self):
return self.front.data연결 큐 전체 소스코드
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데크(Deque)
데큐? 디큐? 데크? 디크? 덱? 무엇이 올바른 발음인지 모르지만 디큐의 경우에는 큐에서 요소를 삭제하는 deQueue와 곂치므로 아니지 않을까... 여하지간 데크와 큐의 차이점은 큐는 rear로 들어와서 front로 나가는 방식을 가졌으나 데크는 rear로 들어오거나 나갈 수 있고, front에서도 들어오거나 나갈 수 있다.
deQueueFromFront <=> enQueueFromFront [ Deque ] enQueueFromRear <=> deQueueFromRear위와 같은 형태로 구성되었다. 따라서 큐의 경우에는 한방향으로 들어오고 나가므로 단순 연결 리스트를 사용했으나 데크의 경우는 이중 연결 리스트를 사용하여 구현하는 것이 이상적이다.
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와 동일하지만 노드의 형태가 다르다. 데크의 구현되어야 할 메서드는 아래와 같다.
- 데크의 공백 상태 검사
- 데크의 앞단에서 원소 삽입
- 데크의 뒷단에서 원소 삽입
- 데크의 앞단에서 원소 삭제
- 데크의 뒷단에서 원소 삭제
연결 큐의 원소 검색
데크의 공백 상태 검사
def isEmpty(self):
if self.front == self.rear:
return True
else:
return False공백 상태 검사는 큐와 동일하게 하였다. 같은 곳을 가리키면 비어있는 상태로 간주한다.
데크의 원소 삽입
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 # 레어를 새노드로 변경데크의 원소 삭제
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데크 전체 소스코드
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 또는 그 반대로 사용하는 경우 기존 큐와 똑같은 작업이 가능하다.
Ghost