연결 리스트(Linked List)를 이용해 큐(Queue) 자료구조를 구현하려면, 새로운 요소를 추가하는 enqueue 연산과 기존 요소를 삭제하는 dequeue 연산에 해당하는 메서드를 각각 정의해야 합니다.
큐는 FIFO(First In, First Out, 선입선출) 방식으로 동작하는 자료구조로, 가장 먼저 들어간 데이터가 가장 먼저 나오게 됩니다. 아래 예제를 통해 실제 구현 방법을 살펴보겠습니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue_structure:
def __init__(self):
self.head = None
self.last = None
def enqueue_operation(self, data):
if self.last is None:
self.head = Node(data)
self.last = self.head
else:
self.last.next = Node(data)
self.last = self.last.next
def dequeue_operation(self):
if self.head is None:
return None
else:
val_returned = self.head.data
self.head = self.head.next
return val_returned
my_instance = Queue_structure()
while True:
print('enqueue <value>')
print('dequeue')
print('quit')
my_input = input('어떤 작업을 수행하시겠습니까? ').split()
operation = my_input[0].strip().lower()
if operation == 'enqueue':
my_instance.enqueue_operation(int(my_input[1]))
elif operation == 'dequeue':
dequeued = my_instance.dequeue_operation()
if dequeued is None:
print('큐가 비어 있습니다.')
else:
print('삭제된 요소 : ', int(dequeued))
elif operation == 'quit':
break
실행 결과
enqueue <value>
dequeue
quit
어떤 작업을 수행하시겠습니까? enqueue 45
enqueue <value>
dequeue
quit
어떤 작업을 수행하시겠습니까? enqueue 12
enqueue <value>
dequeue
quit
어떤 작업을 수행하시겠습니까? dequeue
삭제된 요소 : 45
enqueue <value>
dequeue
quit
어떤 작업을 수행하시겠습니까? quit
코드 설명
먼저 데이터를 저장할 'Node' 클래스를 생성합니다. 각 노드는 data(값)와 next(다음 노드 참조) 속성을 가집니다.
큐의 핵심 기능을 담당하는 'Queue_structure' 클래스를 정의합니다.
이 클래스에는 초기화 함수인 '__init__'이 있으며, 큐의 첫 번째 요소인 'head'와 마지막 요소인 'last'를 'None'으로 초기화합니다.
'enqueue_operation' 메서드는 큐에 값을 추가하는 역할을 합니다. 큐가 비어 있으면 새 노드를 head로 지정하고, 그렇지 않으면 last 뒤에 새 노드를 연결합니다.
'dequeue_operation' 메서드는 큐에서 값을 삭제하고 해당 값을 반환합니다. 큐가 비어 있으면 None을 반환합니다.
'Queue_structure' 클래스의 인스턴스를 하나 생성합니다.
사용자에게 'enqueue', 'dequeue', 'quit' 세 가지 옵션을 제공합니다.
'enqueue' 옵션은 입력받은 특정 값을 큐에 추가합니다.
'dequeue' 옵션은 큐에서 요소를 삭제하고, 삭제된 값을 화면에 출력합니다.
'quit' 옵션은 무한 루프를 종료하여 프로그램을 끝냅니다.
사용자가 입력한 선택지에 따라 해당 연산이 수행되며, 결과는 콘솔에 출력됩니다.
실행 결과에서 확인할 수 있듯이, 먼저 추가한 45가 먼저 삭제되는 것을 볼 수 있습니다. 이는 큐의 선입선출(FIFO) 특성이 올바르게 동작한다는 것을 보여줍니다.