📌큐
자료를 보관할 수 있는 선형 구조
넣을 때에는 한 쪽 끝에서 밀어 넣어야하고(enqueue 인큐 연산) 꺼낼 때에는 반대 쪽에서 뽑아 꺼낸다.(dequeue 디큐 연산)
선입선출(FIFO)특징을 가지는 선형 자료구조다.
큐의 활용
자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우 사용한다. 자료의 생성과 활용을 연결한다.
producer가 생산한 것을 큐에 저장해 순서대로 consumer에게 전달
자료를 생성하는 작업이 여러 곳에서 일어나는 경우
producer1,2가 생성한 자료를 큐에 쌓고 순서대로 consumer에 전달
자료를 이용하는 작업이 여러 곳에서 일어나는 경우
producer가 생성한 자료를 큐에 쌓고 순서대로 consumer1, 2가 먼저 들어온 것부터 빼간다.
자료를 생성하고, 이용하을 여러 곳에서 하는 경우
자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우에도 사용한다.
✍큐의 추상적 자료구조 구현
- 배열을 이용하여 구현
파이썬 리스트와 메서드를 이용
class ArrayQueue:
def __init__(self):
self.data=[]
def size(self): # 큐의 원소수(사이즈)구하기
return len(self.data)
def isEmpty(self): # 큐가 비어있는지를 판단
return self.size() == 0
def enqueue(self, item): # 데이터 원소를 추가
self.data.append(item)
def dequeue(self): # 데이터 원소를 삭제(리턴) 0번 지정 가장 먼저 들어간 것
return self.data.pop(0)
def peek(self): # 큐의 맨 앞 원소 반환
return self.data[0] 배열로 구현한 큐의 연산 복잡도
dequeue() : O(n) -> 배열의 맨 앞 요소를 꺼내고 뒤에서 앞쪽으로 하나씩 당긴다.
나머지 : O(1)
2. 이중 연결리스트를 이용하여 구현
양방향 연결 리스트 이용
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
# 양방향 연결 리스트
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
next = curr.next
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError('Index out of range')
prev = self.getAt(pos - 1)
return self.popAfter(prev)
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
# 양방향 연결 리스트로 구현한 큐
class LinkedListQueue:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size() == 0
def enqueue(self, item):
node = Node(item)
self.data.insertAt(self.data.nodeCount+1, node)
def dequeue(self):
return self.data.popAt(1)
def peek(self):
return self.data.getAt(1).data
def solution(x):
return 0- 연산의 정의
size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
isEmpty() - 현재 큐가 비어 있는지를 판단
enqueue(x) - 데이터 원소 x를 큐에 추가
dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거하며 반환
peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환(제거X)
✍Queue 파이썬 라이브러리
from pythonds.basic.queue import Queue 해서 가져올 수 있음
✍환형 큐(Circular Queue)
정해진 개수의 저장 공간을 빙 돌려가며 이용한다.
rear : 원소를 넣는 곳
front : 원소를 빼는 곳
인덱스0이 제일 앞이 아니고 rear를 새로 추가한 원소를 가리키게 함으로써 앞부분이 변경되며 유지된다. front역시 마찬가지로 원소가 삭제하면 다음으로 원소로 이동 -> 둘 다 리스트 끝에 도착하면 다음 인덱스를 0으로 지정해야한다.
- 배열로 구현한 환형 큐
class CircularQueue:
def __init__(self, n): # 빈 큐를 초기화, 인자로 주어진 최대 큐 길이 설정
self.maxCount = n
self.data = [None] * n
self.count = 0
self.front = -1 # 둘 다 -1로 해야 나중에 편하다.
self.rear = -1
def size(self):
return self.count
def isEmpty(self):
return self.count == 0
def isFull(self): # 큐가 꽉 차 있나?
return self.count == self.maxCount
def enqueue(self, x):
if self.isFull():
raise IndexError('Queue full')
self.rear = (self.rear + 1)%self.maxCount
self.data[self.rear] = x
self.count += 1
def dequeue(self):
if self.isEmpty():
raise IndexError('Queue empty')
self.front = (self.front + 1)%self.maxCount
x = self.data[self.front]
self.count -= 1
return x
def peek(self):
if self.isEmpty():
raise IndexError('Queue empty')
return self.data[(self.front+1)%self.maxCount]
def solution(x):
return 0
- 연결 리스트로 구현한 환형 큐
환형 큐의 추상적 자료구조 구현
- 연산 정의
queue와 같지만 isFull() 이 추가된다.
isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
enqueue, dequeue 후 rear, front 값 변경
환형 큐는 인덱스가 1씩 증가만 하는 것이 아니라 끝을 만나면 다시 처음 (0)으로 돌아온다. if문 보다 정수 나눗셈 (나머지를 구하는 %) 연산을 적용하여 구현한다. self.rear나 self.front 의 값이 1씩 증가하다가 self.maxCount 의 값에 도달하면 0 이 된다.
✍우선순위 큐(Priority Queue)
FIFO방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식이다. 운영체제 CPU 스케줄러 등에 활용된다.
우선순위 큐의 구현
- Enqueue 할 때 우선순위 순서를 유지하도록
- Dequeue 할 때 우선순위 높은 것을 선택
전자가 더 유리하다! 후자로 간다면 Dequeue시 모든 원소를 뒤져야한다.
선형 배열, 연결 리스트 모두 이용 가능하나 중간에 원소 삽입, 삭제가 용이한 연결 리스트를 더 많이 사용한다.
우선 순위 큐의 추상적 자료구조 구현
양방향 연결리스트로 구현
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
next = curr.next
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
prev = self.getAt(pos - 1)
return self.popAfter(prev)
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
class PriorityQueue:
def __init__(self):
self.queue = DoublyLinkedList()
def size(self):
return self.queue.getLength()
def isEmpty(self):
return self.size() == 0
def enqueue(self, x):
newNode = Node(x)
curr = self.queue.head
while curr.next.data != None and x < curr.next.data:
curr = curr.next
self.queue.insertAfter(curr, newNode)
def dequeue(self):
return self.queue.popAt(self.queue.getLength())
def peek(self):
return self.queue.getAt(self.queue.getLength()).data
def solution(x):
return 0