큐 (Queue)
자료 (data element)를 보관할 수 있는 (선형) 구조
선입선출 (FIFO - First-In First-Out) 특징을 가지는 선형 자료구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
-> 인큐(enqueue) 연산
꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음
-> 디큐(dequeue) 연산
큐의 동작
Q = Queue() # 초기 상태 - 비어 있는 큐 (empty queue)
Q.enqueue(A) # 데이터 원소 A를 큐에 추가
Q.enqueue(B) # 데이터 원소 B를 큐에 추가
r1 = Q.dequeue() # A를 꺼냄
r2 = Q.dequeue() # B를 꺼냄
큐의 추상적 자료구조 구현
(1) 배열 (array) 을 이용하여 구현
- Python 리스트와 메서드들을 이용
(2) 연결 리스트 (linked list) 를 이용하여 구현
- 이전 강의에서 마련한 양방향 연결 리스트 이용
연산의 정의
- size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
- isEmpty(): 현재 큐가 비어 있는지를 판단
- enqueue(x): 데이터 원소 x를 큐에 추가
- dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환)
- peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)
배열로 구현한 큐
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): # 데이터 원소를 삭제 (리턴)
return self.data.pop(0)
def peek(self): # 큐의 맨 앞 원소 반환
return self.data[0]
배열로 구현한 큐의 연산 복잡도
연산 | 복잡도 |
size() | O(1) |
isEmpty() | O(1) |
enqueue() | O(1) |
dequeue() | O(n) |
peek() | O(1) |
배열의 맨 앞에 있는 원소를 꺼내는 dequeue() 의 경우, 데이터 원소를 하나 삭제한 후 나머지 원소들을 한칸씩 옮겨줘야 하므로 O(n)
파이썬 라이브러리 사용
from pythonds.basic.queue import Queue
Q = Queue()
dir(Q)
# ['__doc__', '__init__', '__module__', 'dequeue', 'enqueue', 'isEmpty', 'items', 'size']
연습문제 - 이중 연결 리스트로 큐를 구현
연산 복잡도: 모두 O(1)
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.size() + 1, node)
def dequeue(self):
return self.data.popAt(1)
def peek(self):
return self.data.getAt(1).data
def solution(x):
return 0
* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.
'알고리즘 강의' 카테고리의 다른 글
[알고리즘 강의] 파트16. 우선순위 큐(Priority Queues) (0) | 2021.07.19 |
---|---|
[알고리즘 강의] 파트15. 환형 큐(Circular Queues) (0) | 2021.07.19 |
[알고리즘 강의] 파트13. 스택의 응용: 후위 표기 수식 계산 (0) | 2021.07.17 |
[알고리즘 강의] 파트12. 스택의 응용: 수식의 후위 표기법 (0) | 2021.07.16 |
[알고리즘 강의] 파트11. 스택(Stacks) (0) | 2021.07.16 |