Queue
Queue는 데이터를 순차적으로 저장하고 접근하는 자료구조. 가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO(First In First Out) 원칙.
| 동작 | 설명 | 시간복잡도 |
|---|---|---|
| enqueue | Queue의 뒷부분(rear)에 요소를 추가 | O(1) |
| dequeue | Queue의 첫번째 요소(front)를 제거하고 반환. Queue가 비어있으면 데이터를 제거할 수 없음 | O(1) |
| peek | 첫번째 요소를 반환 | O(1) |
| isEmpty | 비어있는지 확인. 데이터가 없으면 True | O(1) |
| size | 요소 수를 반환 |
Array나 Linked List를 사용하여 대기열을 구현.
Queue는 사무실 프린터에 대한 작업 스케줄링을 구현하거나, 전자 티켓에 대한 처리를 주문하거나, 그래프에서 폭 우선 검색을 위한 알고리즘을 만드는 데 사용.
Array를 이용한 Queue
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, element):
self.queue.append(element)
def dequeue(self):
if self.isEmpty(): # 비어있을때 pop(0)을 하면 에러. pop from empty list
return "Queue is empty"
return self.queue.pop(0)
def peek(self):
if self.isEmpty(): # 비어있으면 IndexError: list index out of range
return "Queue is empty"
return self.queue[0]
def isEmpty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Queue 생성
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())Queue: ['A', 'B', 'C']
Dequeue: A
Peek: B
isEmpty: False
Size: 2Array를 이용한 Queue의 장점
- 메모리 효율성 : Array는 LinkedList처럼 다음 요소의 주소를 유지하지 않음.
- 구현 및 이해가 용이함
Array를 이용한 Queue의 단점
- 고정된 크기 : Array는 고정된 크기. Array가 가득 차면 더 이상 요소를 담을 수 없음.
- 이동비용 : dequeue를 사용하면 Queue의 첫번째 요소가 제거되고, 제거된 요소의 자리에 다른 요소가 이동와야함.
Linked List를 이용한 Queue
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None # queue의 앞. dequeue에서 제거되는 부분.
self.rear = None # queue의 뒤. enqueue에서 추가되는 부분.
self.length = 0
def enqueue(self, element):
new_node = Node(element) # 새로운 노드
if self.rear is None: # 빈 LinkedList일때
self.front = self.rear = new_node # 새로운 노드만 있음.
self.length += 1
return
self.rear.next = new_node # 맨 뒤노드의 다음노드를 새노드로 설정
self.rear = new_node # 맨 뒤노드는 새노드가 됨
self.length += 1
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
temp = self.front # 앞부분을 임의저장
self.front = temp.next # 앞부분은 임의저장한 노드의 뒤노드가 됨. temp.next는 None일 수 있음.
self.length -= 1
if self.front is None: # 만약 LinkedList가 비었는지 확인.
self.rear = None
return temp.data # 제거된 요소의 반환.
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.data # 앞부분의 요소 반환
def isEmpty(self):
return self.length == 0
def size(self):
return self.length
def printQueue(self):
temp = self.front # 첫번째 노드를 임시저장
while temp: # tmp가 0이 아닐때까지 while문.
print(temp.data, end=" ") # while문을 순회하면서 요소의 값 출력.
temp = temp.next
# Queue 생성
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())Queue: A B C
Dequeue: A
Peek: B
isEmpty: False
Size: 2Linked List를 이용한 Queue의 장점
- 동적크기 : Array와 달리 동적으로 확장하고 축소할 수 있음.
- 요소의 이동 X : 메모리의 다른 요소를 이동할 필요 없이 큐의 앞쪽 요소를 제거할 수 있음.
Linked List를 이용한 Queue의 단점
- 메모리 : 다음 노드에 대한 주소를 포함해야함.
- 가독성 : Array에 비해 코드가 더 길고 복잡함.
파이썬에서의 deque
Deque(덱, doubled-ended queue)은 양쪽 끝에서 데이터를 추가하거나 삭제할 수 있는 양방향 Queue. Python의 collections 모듈에서 deque 제공. deque는 Linked List로 구현되어있기 때문에 양쪽끝에서 요소 추가/삭제가 list에 비해 빠름.
from collections import deque
# deque 생성 및 초기화
queue = deque()
# Enqueue
queue.append(1). # 오른쪽 끝에 요소 추가
queue.appendleft(2) # 왼쪽 끝에 요소 추가
# iterable
queue.extend([3, 4, 5]) # 오른쪽 끝에 여러 요소 추가
queue.extendleft([-1, 0]) # 왼쪽 끝에 여러 요소 추가
# Dequeue
queue.pop() # 오른쪽 끝 요소 제거
queue.popleft() # 왼쪽 끝 요소 제거
# Front
print(queue[0]) # 첫번째 요소 접근
# IsEmpty
print(true if stack else false)
print(len(a) == 0)
# 회전
queue.rotate(1). # 오른쪽으로 1만큼 회전백준 2164번 카드2 문제 풀어보기
import sys
input = sys.stdin.readline # 입력을 빠르게 받기 위한 설정
from collections import deque
n = int(input())
cards = deque([i for i in range(1, n+1)])
while len(cards) > 1 :
cards.popleft() # 제일 위의 카드 제거
cardsq.append(q.popleft()) # 제일 위의 카드를 제일 아래로 옮김.
# 남은 하나의 카드 출력
print(cards[0])