Queue
특징
큐라는건 대기열이다. 게임을 좀 해보신 분들이라면, 게임을 매칭할때 큐를 돌린다고 표현하는걸 알고있으실거다. 이는 게임매칭의 순서가 먼저 누른사람들끼리 잡아주기 때문이다. (물론 실제로는 그렇지 않다) 큐는 대기열이라 생각하면 조금 쉽게 이해가 될 것이다.
대기열의 가장 큰 특징이라면 FIFO구조이다. First-In, First-Out구조이다.
즉, 먼저 들어온것붙터 나가는것이다. 또한 대기열에서 새치기는 금물이기에, 삽입은 후단 rear에서만 가능하고, 삭제는 전단 front에서만 가능하다.
선형 큐, 원형 큐
우리가 흔히 줄을 설 때는 일렬로 서게된다. 하지만, 컴퓨터에서 선형큐를 사용하게 되면 한가지 문제에 마주하게 된다. 바로 비효율성의 문제이다.
길이5의 대기열이 있고 맨 앞을 front, 맨 뒤를 rear라고 한다고 하자. front와 rear 사이의 공간만큼이 우리가 가지고 있는 공간이다.
이때, 선형큐라면 사람이 한 명 빠지고 나면, front는 한칸 뒤로 이동하게 된다. 이렇게 5회 반복하면 front와 rear가 같아져서 컴퓨터는 이를 공백상태인지 포화상태인지 구분할 수가 없다. 하지만 실제로는 어떠한가? 공간이 5칸이나 남아 있다. 이러한 비효율을 막기위해선 한명이 빠질떄마다 한칸씩 앞으로 이동해야하는데 이 과정은 전 리스트의 복사이기에 O(n)만큼의 시간이 소요된다. 즉 매우 비효율적이다.
따라서 우리는 다음과 같은 원형큐를 사용한다.
원형큐에서는 이동에 따라 rear혹은 front가 이동한다.
이 이동은 다음과 같은 연산을 통해 수행한다
front = (front + 1) % MAX_QSIZE
rear = (rear + 1) % MAX_QSIZE
이 과정은 그림을 보면 이해가 잘 되는데 이는 해당 링크에 잘 나와있다.
원형큐의 구현
MAX_QSIZE = 10
class CircularQueue:
def __init__(self):
self.front = 0
self.rear = 0
self.items = [None] * MAX_QSIZE
def isEmpty(self):
return self.front == self.rear
def isFull(self):
return self.front == (self.rear + 1) % MAX_QSIZE
def clear(self):
self.front = self.rear
def enqueue(self, item):
if not self.isFull():
self.rear = (self.rear + 1) % MAX_QSIZE
self.items[self.rear] = item
def dequeue(self):
if not self.isEmpty():
self.front = (self.front + 1) % MAX_QSIZE
return self.items[self.front]
def peek(self):
if not self.isEmpty():
return self.items[(self.front + 1) % MAX_QSIZE]
def size(self):
return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
def display(self):
out = []
if self.front < self.rear:
out = self.items[self.front + 1:self.rear + 1]
else:
out = self.items[self.front + 1:MAX_QSIZE] + self.items[0:self.rear + 1]
print("f=%s,r=%d ==> " % (self.front, self.rear), out)
- 초기상태는 front = rear = 0 이다. 공간은 미리 설정한 MAX_QSIZE만큼 생성된다.
-
삽입 연산 enqueue
앞서 설명한것처럼 선형큐이기에 rear = (rear + 1) % MAX_QSIZE를 통해 새로운 공간으로 밀어내고, 그 공간에 데이터를 끼워넣는 연산을 수행한다 . -
삭제 연산 enqueue
front는 맨 앞 원소 한칸 앞에 있기때문에, front = (front + 1) % MAX_QSIZE 를 통해 front를 앞으로 한자리 밀어낸다. 그 후 그 값을 리턴해주면 dequeue가 성립한다.
Dequeue
특징
디큐, 혹은 덱 (한글로는 주로 덱이라고 쓰는것같다) 이라고 불리는 이 자료구조는 선출후입 구조였던 queue에서 전단 삽입, 후단 삭제 기능을 추가한 자료구조이다. 여전히 가운데에 접근은 불가능하지만, 전단 혹은 후단에서 추가와 삭제가 모두 가능한 자료구조이다.
- 전단 삭제 front = (front + 1) % MAX_QSIZE
- 후단 삽입 rear = (rear + 1) % MAX_QSIZE
- 전단 삽입 front = (front - 1) % MAX_QSIZE
- 후단 삭제 rear = (rear - 1) % MAX_QSIZE
즉, 기존의 queue 구현에서 두가지 기능만이 추가된 경우이다.
코드 구현
class CircularDeque(CircularQueue):
def __init__(self):
super().__init__()
def addREar(self, item):
self.enqueue(item)
def deletefront(self):
return self.dequeue()
def getFront(self):
return self.peek()
def addFront(self, item):
if not self.isFull():
self.items[self.front] = item
self.front = self.front - 1
if self.front < 0:
self.front = MAX_QSIZE - 1
def deleteRear(self):
if not self.isEmpty():
item = self.items[self.rear]
self.rear = self.rear - 1
if self.rear < 0: self.rear = MAX_QSIZE - 1
return item
def getRear(self):
return self.items[self.rear]- 기존의 queue와 같은 코드를 사용하는 경우는 작성하지 않았다.
- 전단 삽입
def addFront(self, item):
if not self.isFull():
self.items[self.front] = item
self.front = self.front - 1
if self.front < 0:
self.front = MAX_QSIZE - 1위에서 설명한것처럼 아무것도 안한 상태의 front은 현 최전단 원소의 한칸 위에 있다. 따라서 전단에 삽입하기 위해서는 self.item의 front 인덱스에 현 아이템을 집어넣게된다. 그 후 front를 반시계 방향으로 돌려야하기에 front -1을 통해 한칸 이동시킨다.
만약 self.front가 해당과정을 통해서 0 보다 작아졌다면, 원형 리스트의 범위를 벗어나 끝으로 돌아간것이기에 (오버플로우를 생각하면 된다) MAX_QSIZE - 1로 보내주면 된다.
- 후단 삭제
def deleteRear(self):
if not self.isEmpty():
item = self.items[self.rear]
self.rear = self.rear - 1
if self.rear < 0: self.rear = MAX_QSIZE - 1
return item아무것도 안한 상태의 rear는 현재 최후단의 인덱스와 동일하다. 따라서 후단에서 삭제를 하고 그 값을 반환하려면 일단 반환값을 저장한다.
그 후 위의 전단삽입과 마찬가지 과정으로 rear = rear -1 을 해주거나, MAX_QSIZE - 1을 수행하면 된다.
정리
이처럼 큐, 디큐는 서로간의 큰 차이가 없고 구현에 있어서도 대부분의 코드와 원리를 공유한다. 이 원형큐의 원리를 이해하는것이 큐의 이해에 있어서 핵심이라 할 수 있다.
Circular Linked Queue
원형연결큐이다. 즉 연결리스트로 큐를 구현하는것이다.
특징
다른 연결된 리스트들이 가지는 특징을 가진다.
구현
class Node:
def __init__(self, elem, link=None):
self.data = elem
self.link = link
class CircularLinkedQueue:
def __init__(self):
self.tail = None
def isEmpty(self):
return self.tail is None
def clear(self):
self.tail = None
def peek(self):
if not self.isEmpty():
return self.tail.link.data
def enqueue(self, item): # time complexity O(1)
node = Node(item, None)
if self.isEmpty(): # when queue is empty
node.link = node
self.tail = node
else:
node.link = self.tail.link # new node link is now pointing front
self.tail.link = node # the previous link is now connected to node
self.tail = node # tail is pointing the last node
def dequeue(self): # time complexity O(1)
if not self.isEmpty():
data = self.tail.link.data
if self.tail.link == self.tail:
self.tail = None
else:
self.tail.link = self.tail.link.link
return data
def size(self):
if self.isEmpty():
return 0
else:
count = 1
node = self.tail.link
while not node == self.tail:
node = node.link
count += 1
return count
def display(self, msg = 'CircularLinkedQueue:'):
print(msg, end = '')
if not self.isEmpty():
node = self.tail.link
while not node == self.tail:
print(node.data, end = ' ')
node = node.link
print(node.data, end='')
print()enqueue
def enqueue(self, item): # time complexity O(1)
node = Node(item, None)
if self.isEmpty(): # when queue is empty
node.link = node
self.tail = node
else:
node.link = self.tail.link # new node link is now pointing front
self.tail.link = node # the previous link is now connected to node
self.tail = node # tail is pointing the last node연결리스트에 후위삽입을 할 때 우리가 원형큐에서 후위를 하나 뒤로 미룬것처럼, 서로간의 링크르 바꿔주는 과정이 필요하다.
우선적으로 아무것과도 연결되지 않은 Node를 하나 생성한다
-
만약 비어있는 큐에 집어넣을 경우
비어있는 경우 node.link를 자기자신을 지칭하게 되고, self.tail 즉, rear가 node를 연결하도록 바꿔준다. -
비어있지 않은 경우
node의 링크는 self.tail.link (rear의 링크) 즉, front와 연결해준다.
그 후, self.tail.link는 node를 지칭하도록 바꿔주고, self.tail은 노드를 연결해서 rear를 하나 뒤로 이동하듯, tail을 바꿔준다.
dequeue
def dequeue(self): # time complexity O(1)
if not self.isEmpty():
data = self.tail.link.data
if self.tail.link == self.tail:
self.tail = None
else:
self.tail.link = self.tail.link.link
return data삭제 연산에서도 마찬가지로 front를 뒤로 한칸 미뤄주는 연산이 필요하다
우선 반환할 데이터를 저장한다. 해당 데이터는 self.tail.link(front).data 이다.
그 후 만약
1. self.tail.link == self.tail 즉, 항목이 하나만 있는 경우라면 self.tail 값을 none으로 바꾼다. 리스트가 empty상태로 만들기 위해서다.
- 그렇지 않다면, self.tail.link 는 self.tail.link의 link, self.tail.link.link(front +1)로 바꿔준다.
display
def display(self, msg = 'CircularLinkedQueue:'):
print(msg, end = '')
if not self.isEmpty():
node = self.tail.link
while not node == self.tail:
print(node.data, end = ' ')
node = node.link
print(node.data, end='')
print()그 외의 특징적인 코드는 display 코드이다.
node를 self.tail.link front로 설정하고 node가 self.tail에 도달하기 전까지 지속적으로 node.link로 갱신해가며 프린트하는 방식이다.
DoubleLinkedDequeue
Single Linked List가 Node 가 있고 이 노드에 다음 노드를 연결하는 링크가 있다는 것 정도는 이제 다들 알고있는 사실이다. 그렇다면 흔히들 덱, 디큐 라고 부르는 자료구조도 이렇게 표현 할 수 있을까?
하라고 하면 안될건 없지만, 선형큐가 보여준것처럼 이 또한 비효율적이다. 왜? Dequeue는 선입선출, 후입선출 같은 구조가 아니라 양방향 삽입이 가능하고 삭제연산도 양방향에서 가능한 연산이기 떄문이다.
지금까지의 자료구조들이 한쪽으로만 갈고리를 걸어둔 자료구조였다면, Dequeue는 서로가 서로에게 갈고리를 거는 자료구조이다.
특징
특징은 다른 연결리스트들과 비슷하다. 다만 Data, Link의 구성이던 기존의 노드와 다르게 앞 뒤로 연결을 해야하기에 Data, Next, Prev 총 3가지로 구성되어있다.
따라서 이에 맞는 새로운 DNode 클라스가 필요하다.
DNode 클라스
class DNode:
def __init__(self, elem, prev=None, next=None):
self.data = elem
self.prev = prev
self.next = next
data 에는 입력 elem을, 그리고 prev, next에는 각각 맞는 링크를 넣어준다. 다만 막 생성한 노드는 연결이 되어있지 않기에 기본값을 None으로 둔다
코드로 구현한 Doubly Linked List
class DNode:
def __init__(self, elem, prev=None, next=None):
self.data = elem
self.prev = prev
self.next = next
class DoublyLinkedDequeue:
def __init__(self):
self.front = None
self.rear = None
def isEmpty(self):
return self.front is None
def clear(self):
self.front = self.rear = None
def size(self):
if self.isEmpty():
return 0
count = 0
node = self.front
while node is not None:
node = node.next
count += 1
return count
def display(self, msg = 'DoubleLinkedDequeue: '):
print(msg, end = '')
if not self.isEmpty():
node = self.front
while node is not None:
print(node.data, end = ' ')
node = node.next
print(node.data, end='')
print()
def addFront(self, item):
node = DNode(item, None, self.front)
if self.isEmpty():
self.front = self.rear = node
else:
self.front.prev = node
self.front = node
def addRear(self, item):
node = DNode(item, self.rear, None)
if self.isEmpty():
self.front = self.rear = node
else:
self.rear.next = node
self.rear = node
def deleteFront(self):
if not self.isEmpty():
data = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
else:
self.front.prev = None
return data
def deleteRear(self):
if not self.isEmpty():
data = self.rear
self.rear = self.rear.prev
if self.rear is None:
self.front = None
else:
self.rear.next = None
return data기존의 연결리스트 스택이나, 연결리스트 큐가 head pointer를 가지고 있던것을 기억하는가?
그와 마찬가지로 Deque도 head Pointer가 있지만, 이중연결이기에 tail Pointer도 있다.
바뀐게 많은 만큼, 하나씩 전부 살펴보도록 하겠다.
init
initialization을 위한 코드이다. Double Linkedlist의 특성상, front와 rear를 가지고 있다.
addFront
전단삽입 기능을 하는 함수이다. 우선 DNode를 생성한다. 이떄 DNode는 최전방 노드가 될 노드이기에 prev는 None으로 설정하고, Next는 현 head Pointer 즉, 추가 되기전 최전방 노드의 정보를 저장한다.
그 후, 만약 리스트가 비어있는 리스트면, 포인터를 전부 현 노드에 맞춘다. 그렇지 않다면 self.front.prev 즉, 현 최전방 노드의 이전값을 추가 될 Node로 설정해주고 최전방 노드 포인터를 현 노드에 맞춰준다.
addRear
후방삽입 기능을 하는 함수이다. 우선 DNode를 생성한다. 이떄 DNode는 최후방 노드가 될 노드이기에, prev를 현 최후방 노드값으로 설정하고 next는 공백으로 둔다.
그 후, 만약 리스트가 비어있다면, 포인터를 전부 현 노드에 맞추고 그렇지 않다면, 현 최후방 노드의 next링크를 추가되는 노드로 맞추고 최후방 포인터를 추가node로 가게 한다.
deleteFront
전방삭제 연산을 하는 함수이다.
과정은 다음과 같다.
1. 삭제할 노드의 data를 data에 저장한다
2. 최전방 노드 포인터를 삭제할 다음 노드로 이동시킨다.
3. 만약 삭제 후 리스트가 비어버리면 최후방포인터도 None으로 설정한다
4. 그렇지 않다면 현 최전방 포인터가 지목하는 노드의 prev링크를 None으로 한다.
5. 데이터를 반환한다.
deleteRear
후방삭제를 하는 연산이다.
전체적으로 deleteFront와 유사하다.
1. 삭제할 노드의 data를 data에 저장한다
2. 최후방 노드 포인터를 삭제할 노드의 이전 노드로 이동시킨다.
3. 만약 삭제 후 리스트가 비어버리면 최전방포인터도 None으로 설정한다
4. 그렇지 않다면 현 최후방 포인터가 지목하는 노드의 next링크를 None으로 한다.
5. 데이터를 반환한다.
마치며
이로써 우리는 리스트, 스택, 큐 , 덱 4가지 자료구조를 각각 리스트, 연결리스트로 구현하는 걸 모두 마무리했다.
이제 정렬과 탐색의 시간이다.
