파이썬을 사용하여 스택, 큐를 구현하는 방법을 다루고 있습니다. 이번 글을 작성하며 파이썬에는 포인터가 없어서 자료 구조를 어떻게 구현할까 싶었던 의문점이 풀렸습니다.
2025. 1. 30 최초작성
링크드 리스트(Linked List)
스택(Stack)
큐(Queue)
링크드 리스트(Linked List)
파이썬은 기본적으로 포인터를 직접적으로 사용할 수 있는 언어가 아니지만, 객체 참조를 통해 간접적으로 포인터와 유사한 방식으로 동작할 수 있습니다. 파이썬에서 모든 변수는 객체에 대한 참조(reference)로 작동하며, 이는 C/C++의 포인터와 개념적으로 유사합니다.
링크드 리스트(Linked List) 구조를 사용하여 포인터처럼 동작하도록 구현할 수 있습니다. 링크드 리스트에서 각 노드에 포함되어 있는 next 변수가 포인터 역할을 하여 다음 노드를 가리킵니다.
이제 스택과 큐를 구현해봅니다. 파이썬에 포인터가 없지만 편의상 포인터라고 서술하고 있습니다.
스택(Stack)
이를 활용하여 스택을 구현해보겠습니다.
| # 클래스 Node의 data 멤버 변수가 데이터를 저장하고, next 멤버변수가 참조(포인터)를 사용하여 다음 노드를 가리킵니다. class Node: def __init__(self, data=None): self.data = data # 노드의 데이터 self.next = None # 다음 노드를 가리킬 포인터 (참조) # 클래스 Stack의 top 멤버 변수가 포인터 역활을 하여 스택의 맨 위 노드를 가리킵니다. class Stack: def __init__(self): self.top = None # 스택의 가장 위에 있는 노드 # 스택이 비어있는지 여부를 리턴합니다. def is_empty(self): return self.top is None # 스택에 데이터를 삽입합니다. def push(self, item): new_node = Node(item) # 새 노드를 생성 new_node.next = self.top # 새 노드는 기존 top을 가리킴 self.top = new_node # top을 새 노드로 갱신 # 스택에서 데이터를 하나 꺼냅니다. def pop(self): if not self.is_empty(): popped_item = self.top.data # top 노드의 데이터를 가져옴 self.top = self.top.next # top을 다음 노드로 갱신 return popped_item else: return "스택이 비어 있습니다." # 스택의 크기를 반환합니다. def size(self): current = self.top count = 0 while current: count += 1 current = current.next return count # 스택의 모든 요소를 출력합니다. def display(self): """스택의 모든 요소를 출력하는 메서드""" elements = [] current = self.top while current: elements.append(str(current.data)) current = current.next return '->'.join(elements) if elements else "빈 스택" # 스택을 사용해봅니다. stack = Stack() # 스택에 데이터 삽입 stack.push(1) stack.push(2) stack.push(3) print("스택 내용:", stack.display()) print("요소 제거:", stack.pop()) print("스택 크기:", stack.size()) print("스택이 비었나요?:", stack.is_empty()) print("최종 스택 내용:", stack.display()) |
실행결과입니다.
스택 내용: 3->2->1
요소 제거: 3
스택 크기: 2
스택이 비었나요?: False
최종 스택 내용: 2->1
큐(Queue)
큐(Queue)는 FIFO(First In, First Out), 즉 먼저 들어온 데이터가 먼저 나오는*구조입니다. 이를 링크드 리스트로 구현하려면 두개의 포인터가 필요합니다. 하나는 큐의 front(앞쪽) 노드를, 다른 하나는 큐의 rear(뒤쪽) 노드를 가리킵니다.
| # 클래스 Node의 data 멤버 변수가 데이터를 저장하고, next 멤버변수가 참조(포인터)를 사용하여 다음 노드를 가리킵니다. class Node: def __init__(self, data=None): self.data = data # 노드의 데이터 self.next = None # 다음 노드를 가리킬 포인터 (참조) class Queue: def __init__(self): self.front = None # 큐의 앞쪽 노드를 가리킬 포인터 self.rear = None # 큐의 뒤쪽 노드를 가리킬 포인터 # 큐가 비어있는지 여부를 리턴합니다. def is_empty(self): return self.front is None # 큐에 데이터를 삽입하면 rear 포인터의 위치가 조정됩니다. def enqueue(self, item): new_node = Node(item) if self.rear is None: # 큐가 비어 있을 경우 self.front = self.rear = new_node else: self.rear.next = new_node # 기존의 rear 노드의 next가 새 노드를 가리키게 함 self.rear = new_node # rear를 새 노드로 갱신 # 큐에서 데이터를 제거하면 front 포인터의 위치가 조정됩니다. def dequeue(self): if not self.is_empty(): dequeued_item = self.front.data # front 포인터가 가리키는 노드의 데이터를 꺼내게 됩니다. self.front = self.front.next # front 포인터를 다음 노드로 갱신 if self.front is None: # 큐가 비었으면 rear도 None으로 설정 self.rear = None return dequeued_item else: return "큐가 비어 있습니다." # 큐의 크기를 계산합니다. def size(self): current = self.front count = 0 while current: count += 1 current = current.next return count def display(self): if self.is_empty(): return "큐가 비어 있습니다." current = self.front elements = [] while current: elements.append(str(current.data)) current = current.next return " -> ".join(elements) queue = Queue() # 큐에 데이터 삽입 queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) print('큐 내용:', queue.display()) print('요소 제거', queue.dequeue()) print('큐 크기', queue.size()) print('큐가 비었나요?', queue.is_empty()) print('최종 큐 내용:', queue.display()) |
실행결과입니다.
큐 내용: 1 -> 2 -> 3
큐 맨앞 노드 요소 1
요소 제거 1
큐 크기 2
큐가 비었나요? False
최종 큐 내용: 2 -> 3
시간날때마다 틈틈이 이것저것 해보며 블로그에 글을 남깁니다.
블로그의 문서는 종종 최신 버전으로 업데이트됩니다.
여유 시간이 날때 진행하는 거라 언제 진행될지는 알 수 없습니다.
영화,책, 생각등을 올리는 블로그도 운영하고 있습니다.
https://freewriting2024.tistory.com
제가 쓴 책도 한번 검토해보세요 ^^
