[자료구조/알고리즘] 큐(Queue)와 덱(Deque)
큐(Queue)
- FIFO(선입선출) 형식의 자료구조
- 먼저 들어온 데이터가 순서대로 먼저 나가는 구조입니다.
스택과 다르게 한쪽에서 데이터가 추가되고, 다른 한쪽에서 데이터가 삭제되는 구조입니다.
리스트를 이용한 큐 구현
- enqueue : 큐의 맨 뒤쪽에 항목 삽입
- dequeue : 큐 맨 앞쪽의 항목을 반환하고 제거
- peek/front : 큐의 맨 앞쪽 항목을 조회
- empty : 큐가 비었는지 확인
- size : 큐의 크기를 확인
# 리스트를 이용한 Queue 구현
class Queue(object):
def __init__(self):
self.items = [] # 값을 담아줄 큐 배열
# 큐가 비었는지 확인하는 함수(Empty : True / Not Empty : false)
def isEmpty(self):
return not self.items
def dequeue(self):
# 큐가 비어있다면
if self.isEmpty():
print("Queue is Empty!")
# 그렇지 않으면
else:
value = self.items.pop(0) # 큐 배열의 0번째 값을 반환
return value
def enqueue(self, item):
self.items.append(item) # 큐 배열의 맨 뒤에 값을 삽입
def size(self):
return len(self.items) # 큐 배열의 크기를 반환
def peek(self):
if self.isEmpty():
print("Queue is Empty!")
else:
return self.items[0]
def __repr__(self):
return repr(self.items)
if __name__ == "__main__":
queue = Queue()
print("큐가 비었습니까? {}".format(queue.isEmpty()))
print("큐에 값을 추가합니다.")
for i in range(10):
queue.enqueue(i)
print("Queue : {}".format(queue))
print("큐의 크기 : {}".format(queue.size()))
print("peek : {}".format(queue.peek()))
print("dequeue : {}".format(queue.dequeue()))
print("peek : {}".format(queue.peek()))
print("Queue : {}".format(queue))
큐가 비었습니까? True
큐에 값을 추가합니다.
Queue : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
큐의 크기 : 10
peek : 0
dequeue : 0
peek : 1
Queue : [1, 2, 3, 4, 5, 6, 7, 8, 9]
노드를 이용한 큐(Queue) 구현
- 노드를 이용해서 SingleLinkedList로 구현합니다.
# Node를 이용해 큐 구현
class Node(object):
def __init__(self, value = None, pointer = None):
self.value = value
self.pointer = pointer
class LinkedQueue(object):
def __init__(self):
self.head = None # 큐의 맨 앞
self.tail = None # 큐의 맨 뒤
self.count = 0
def isEmpty(self):
return not bool(self.head)
def dequeue(self):
if self.isEmpty():
print("Queue is Empty!")
else:
node = self.head
self.head = self.head.pointer
self.count -= 1
if self.head is None: # 데이터를 삭제함으로써 큐가 빌 경우
# head와 tail은 같은 노드를 바라보고 있었으므로
self.tail = None # tail값도 비워주기
return node.value
def enqueue(self, value):
node = Node(value)
if not self.head: # head가 비어있다면
self.head = node
self.tail = node
else:
self.tail.pointer = node # 현재 tail의 포인터를 node와 연결
self.tail = node # 연결된 node를 tail로 지정
self.count += 1
def size(self):
return self.count
def peek(self):
if self.head:
return self.head.value
else:
print("Queue is Empty!")
def printQueue(self):
node = self.head
while node:
print(node.value, end = " ")
node = node.pointer
print()
if __name__ == "__main__":
queue = LinkedQueue()
print("스택이 비었습니까? {0}".format(queue.isEmpty()))
print("스택에 값을 추가합니다.")
for i in range(10):
queue.enqueue(i)
queue.printQueue()
print("큐의 크기는? {0}".format(queue.size()))
print("peek : {}".format(queue.peek()))
print("pop : {}".format(queue.dequeue()))
print("peek : {}".format(queue.peek()))
queue.printQueue()
# for i in range(9):
# queue.dequeue()
# print(queue.tail)
스택이 비었습니까? True
스택에 값을 추가합니다.
0 1 2 3 4 5 6 7 8 9
큐의 크기는? 10
peek : 0
pop : 0
peek : 1
1 2 3 4 5 6 7 8 9
LinkedQueue의 head는 큐의 맨 앞, tail은 맨 뒤를 의미합니다.
Enqueue(데이터 추가)할 때는 데이터 값을 노드 형식(value, pointer)으로 변수 node에 대입한 후
head가 비어있다면 > 큐에서 유일한 값이 되므로 head와 tail이 모두 추가된 node를 가리키게 됩니다.
head가 비어있지 않을땐 > 들어오는 값을 큐에 우선 연결해준 후, tail의 위치를 마지막으로 변경해주면 됩니다.
tail의 다음값으로 지정하기 위해 우선 기존의 tail.pointer에 변수 node를 넣어주고, 추가된 노드를 tail로 지정해줍니다.
Dequeue(데이터 삭제)할 때는 큐의 맨 앞, head를 반환해주기 위해 임시 node변수에 대입합니다.
그 후, head에 head.pointer(즉, 기존 head에서 가리키는 다음 노드)를 넣어줍니다.
마지막으로 임시 node에 저장된 기존 head값을 return해주기 전에!
큐의 유일한 노드가 삭제 될 경우는 head와 tail이 그 노드를 동시에 바라보고 있었기 때문에
tail도 None으로 초기화 해주어야 합니다.
덱(Deque)
- 덱(Double Ended Queue)은 큐와 다르게 양쪽 끝에서 항목을 조회, 삽입, 삭제가 가능합니다.
(스택과 큐의 융합) - 위에서 구현했던 큐 리스트를 그대로 상속해서 덱을 구현해보겠습니다.
# 리스트를 활용한 덱 구현
class Deque(Queue): # 큐 리스트를 상속
# enqueue 반대로 하기
def enqueue_front(self, item):
self.items.insert(0, item) # 리스트 0번째에 값 추가
# dequeue 반대로 하기
def dequeue_back(self):
if self.isEmpty():
print("Queue is Empty!")
else:
value = self.items.pop() # 리스트 가장 뒤에 있는 값을 삭제, 반환
return value
if __name__ == "__main__":
deque = Deque()
print("덱이 비었습니까? {}".format(deque.isEmpty()))
print("덱에 값을 추가합니다.")
for i in range(1,20,2):
deque.enqueue(i)
print("덱 : {}".format(deque))
print("peek : {0}".format(deque.peek()))
print("dequeue : {0}".format(deque.dequeue()))
print("덱 : {0}".format(deque))
deque.enqueue_front(50)
print("덱 : {0}".format(deque))
print("dequeue_back : {}".format(deque.dequeue_back()))
print("덱 : {0}".format(deque))
덱이 비었습니까? True
덱에 값을 추가합니다.
덱 : [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
peek : 1
dequeue : 1
덱 : [3, 5, 7, 9, 11, 13, 15, 17, 19]
덱 : [50, 3, 5, 7, 9, 11, 13, 15, 17, 19]
dequeue_back : 19
덱 : [50, 3, 5, 7, 9, 11, 13, 15, 17]
덱 모듈 사용하기
- Python의 Collections 모듈 안에 Deque라는 클래스가 이미 구현되어 있습니다.
- Deque 클래스는 이중 연결 리스트(Double Linked List)로 구성되어서 여러 기능을 효율적으로 사용이 가능합니다.
# 덱 모듈 사용하기
from collections import deque
# deque() : 덱 생성
q = deque(["Apple", "Banana", "Peach"])
print(q)
# 오른쪽에 값을 추가
q.append("Strawberry")
print(q)
# 왼쪽에 값을 추가
q.appendleft("Mango")
print(q)
# 왼쪽의 값을 반환
q.popleft()
print(q)
# 오른쪽의 값을 반환
q.pop()
print(q)
# rotate(n) : n의 길이만큼 양수면 오른쪽, 음수면 왼쪽으로 값들이 이동
q = deque(['Mango', 'Apple', 'Banana', 'Peach', 'Strawberry'])
q.rotate(2)
print(q)
q.rotate(-1)
print(q)
# collections안의 Deque은 이중 연결 리스트 형식으로 되어져있기 때문에
# 이러한 기능이 가능합니다.
deque(['Apple', 'Banana', 'Peach'])
deque(['Apple', 'Banana', 'Peach', 'Strawberry'])
deque(['Mango', 'Apple', 'Banana', 'Peach', 'Strawberry'])
deque(['Apple', 'Banana', 'Peach', 'Strawberry'])
deque(['Apple', 'Banana', 'Peach'])
deque(['Peach', 'Strawberry', 'Mango', 'Apple', 'Banana'])
deque(['Strawberry', 'Mango', 'Apple', 'Banana', 'Peach'])
댓글남기기