✏️ Stack
스택은 LIFO 규칙을 가지고 있는 리스트입니다.
LIFO란, Last In, First Out 입니다. 나중에 들어온 데이터가 먼저 나가는 규칙입니다. 즉 먼저 들어온 데이터가 나중에 나가는 구조입니다.
일상 생활 예시로는 책을 쌓아놓으면 가장 위에부터 빼야하는 구조, 엘르베이터를 타면 처음 탄 사람이 마지막에 내리는 구조를 생각할 수 있습니다.
스택은 이전에 배웠던 배열과 연결리스트로 구현할 수 있는데 우리는 연결리스트로 스택을 구현할 겁니다.
이런식으로 첫번째 인덱스 즉, head에 새로운 자료를 넣어주면 됩니다.
데이터를 제거할 때도 head 부분부터 차례대로 제거하면 간단하게 스택이 됩니다.
스택은 괄호의 개수가 알맞은지 웹 사이트에서 뒤로 가기 또는 앞으로 가기를 할 때 등 사용합니다.
시스템 내부에서는 대표적으로 스택 프레임에 사용됩니다.
이런식으로 스택에 저장되었다가 함수가 끝나면 스택 메모리에 있던 스택 프레임이 없어지게 됩니다.
스택의 주요 동작은 다음과 같습니다.
push는 데이터를 맨 위로 삽입하는 기능
pop은 맨 위 데이터를 꺼내는 기능
peek은 맨 위 데이터의 값을 참조하는 기능을 합니다. (꺼내지는 않음)
자세한 동작은 구현 부분에서 알아보도록 합시다.
Stack 구현
# import 생략
class MyStack:
def __init__(self):
self.list = MyLinkedList()
def push(self, value):
"""스택의 맨 위에 요소를 추가합니다."""
self.list.add_at_index(0, value)
def pop(self):
"""스택의 맨 위 요소를 제거하고 반환합니다."""
try:
return self.list.remove_at_index(0)
except IndexError:
return None
def peek(self):
"""스택의 맨 위 요소를 반환합니다. 제거하지는 않습니다."""
try:
return self.list.get(0)
except IndexError:
return None
def is_empty(self):
"""스택이 비어 있는지 여부를 반환합니다."""
return self.list.size == 0# import 생략
stack = MyStack()
print("===== 첫 번째 출력 =====")
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack.pop()) # 4
print(stack.pop()) # 3
print(stack.pop()) # 2
print(stack.pop()) # 1
print("===== 두 번째 출력 =====")
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack.peek()) # 4
stack.pop()
print(stack.peek()) # 3
print(f"isEmpty: {stack.is_empty()}") # False
stack.pop()
stack.pop()
stack.pop()
print(f"isEmpty: {stack.is_empty()}") # True
# 빈 스택에서 pop 테스트
print(stack.pop()) # None
결과
===== 첫 번째 출력 =====
4
3
2
1
===== 두 번째 출력 =====
4
3
isEmpty: false
isEmpty: true
None✏️ Queue
Queue도 Stack과 같이 단순한 규칙을 가지고 있는 리스트입니다.
바로, FIFO(First In, First Out) 구조를 가지고 있습니다. 즉, 먼저 들어간 것이 먼저 나오는 특징을 가지고 있습니다.
일상 생활에서 마트에서 줄을 설 때 처음 온 사람이 먼저 계산을 마치고 나가는 모습을 볼 수 있습니다. 이 처럼 줄을 스는 경우가 Queue에 해당됩니다.
Quque의 사례 중 producer/consumer archetecture에서도 Queue가 사용됩니다. 다음과 같이 Producer가 데이터를 만들고 Queue에 넣으면 Consumer가 이를 꺼내 사용하는 구조입니다.
Queue 역시 연결 리스트로 구현할 겁니다.
1,2,3,4를 순서대로 head에 삽입하면 됩니다.
이제 가장 먼저 들어간 1을 제거하려면 어디서부터 데이터를 삭제해야 될까요?
마지막부터 데이터를 제거하면 됩니다.
이것이 Queue의 전부 입니다.
하지만 여기서 구현을 생각하면 약간의 문제가 생깁니다.
우리가 구현한 연결 리스트는 단방향 연결리스트로 헤드를 이용하면 첫번째 위치에 데이터를 삽입하는 것은 간단합니다. 그러나 이런 구조에서 데이터를 뒤에서 제거하는 것은 힘듭니다.
왜 일까요? 데이터를 삭제하기 위해서 첫 번째 데이터부터 마지막 데이터까지 순서대로 타고 가야 하기 때문입니다. 따라서 O(n)의 성능을 갖게 됩니다.
성능을 위해서 tail 변수를 하나 만들어 봅시다. tail은 맨 마지막 노드를 가리킵니다.
이렇게 하면 O(1) 성능으로 노드를 제거할 수 있게 됩니다.
하지만 tail 변수만 추가한다고 계속 O(1)의 성능을 가지는 것은 아닙니다. tail을 이용해서 데이터를 제거 할 때 tail을 가리키던 노드는 삭제하면 그만이지만 삭제된 이전 노드를 다시 tail로 설정해줘야 합니다.
하지만 우리가 만든 연결 리스트는 다음 노드만 가리키는 단방향 연결 리스트이기 때문에 tail로 이전 노드를 참조하는 것은 불가능합니다.
따라서 tail을 다시 마지막 노드로 설정해주기 위해서는 head부터 순서대로 마지막 노드까지 가야하기 때문에 O(n)의 성능을 가집니다.
따라서 이중 연결 리스트로 이전 노드를 참조할 수 있도록 수정한다면 tail 이전 노드를 tail로 재할당 할 수 있게 됩니다.
기술 문서에서 Queue를 만났을 때 tip
기술 문서에서 Queue가 항상 FIFO를 의미하지는 않습니다. 어쩔 때는 그냥 데이터를 저장해놓는 자료구조 정도로 해석이 될 때도 있습니다. 문맥을 잘 파악해서 FIFO 구조를 갖는 Queue를 의미하는지 데이터를 단순히 저장해놓는 Queue를 의미하는지 잘 해석하시기 바랍니다.
Stack/Queue 관련 에러와 해결 방법
Stack
다음과 같이 재귀함수를 실행 했을 때 스택 프레임에 일정 메모리를 넘기게 될 경우 에러를 발생하게 됩니다.
Queue
이를 해결하기 위해 Queue 사이즈를 고정하는 방법이 있습니다.
그렇다면 Queue가 다 찼을 때는 어떻게 해야 할까요?
자바에서 이를 제공하는 구현체로 LinkedBlockingQueue가 존재합니다.
add : 예외를 던집니다.
offer : 특별한 값(null or false)를 반환합니다.
put : 성공할 때까지 영원히 쓰레드를 블락(Block)합니다.
offer(time, unit) : 제한된 시간만 블락되고 그래도 안되면 포기합니다.
Queue 구현
class MyDoublyLinkedList(MyList):
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def add_value(self, value):
self.add_at_index(self.size, value)
def add_at_index(self, index, value):
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
new_node = self.Node(value)
if index == 0:
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
elif index == self.size:
new_node.prev = self.tail
if self.tail:
self.tail.next = new_node
self.tail = new_node
else:
current_node = self.head
for _ in range(index - 1):
current_node = current_node.next
new_node.next = current_node.next
new_node.prev = current_node
if current_node.next:
current_node.next.prev = new_node
current_node.next = new_node
if new_node.next is None:
self.tail = new_node
self.size += 1
def index_of(self, value):
index = 0
current_node = self.head
while current_node:
if current_node.value == value:
return index
current_node = current_node.next
index += 1
return -1
def last_index_of(self, value):
index = -1
current_node = self.head
idx = 0
while current_node:
if current_node.value == value:
index = idx
current_node = current_node.next
idx += 1
return index
def remove_at_index(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
current_node = self.head
if index == 0:
removed_value = current_node.value
self.head = self.head.next
if self.head:
self.head.prev = None
if self.head is None:
self.tail = None
elif index == self.size - 1:
removed_value = self.tail.value
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
if self.tail is None:
self.head = None
else:
for _ in range(index):
current_node = current_node.next
removed_value = current_node.next.value
current_node.next = current_node.next.next
if current_node.next:
current_node.next.prev = current_node
self.size -= 1
return removed_value
def remove_value(self, value):
index = self.index_of(value)
if index == -1:
return False
self.remove_at_index(index)
return True
def get(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
current_node = self.head
for _ in range(index):
current_node = current_node.next
return current_node.value
def clear(self):
self.head = None
self.tail = None
self.size = 0
def print_all(self):
result = []
current_node = self.head
while current_node:
result.append(current_node.value)
current_node = current_node.next
print(result)class MyQueue:
def __init__(self):
self.list = MyDoublyLinkedList()
def enqueue(self, value):
self.list.add_at_index(0, value) # 리스트의 맨 앞에 값을 추가 (enqueue)
def dequeue(self):
try:
# 리스트의 맨 뒤 값을 제거 (dequeue)
return self.list.remove_at_index(self.list.size - 1)
except Exception as e:
return None # 예외가 발생하면 None 반환
def front(self):
# 큐의 맨 앞 요소를 반환 (head)
if not self.is_empty():
return self.list.head.value
return None
def is_empty(self):
# 리스트가 비어 있으면 True 반환
return self.list.size == 0queue = MyQueue()
print("===== enqueue() 세 번 호출 =====")
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("Front element:", queue.front())
print("===== dequeue() 네 번 호출 =====")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue()) # 큐가 비어 있는 상태에서 호출
print("isEmpty:", queue.is_empty())결과
===== enqueue() 세 번 호출 =====
Front element: 1
===== dequeue() 네 번 호출 =====
1
2
3
None
isEmpty: true✏️ Deque
Deque는 데이터의 삽입과 제거를 헤드와 테일 두 군데서 자유롭게 할 수 있는 자료구조 입니다. 즉, 앞 뒤로 데이터를 삽입하고 제거할 수 있습니다.
Deque 구현
#import 생략
class Deque:
def __init__(self):
self.list = MyDoublyLinkedList()
def add_first(self, value):
"""Deque의 앞에 값을 추가"""
self.list.add_at_index(0, value)
def remove_first(self):
"""Deque의 앞에서 값을 제거"""
if self.list.size == 0:
return None # Deque가 비어 있으면 None 반환
return self.list.remove_at_index(0)
def add_last(self, value):
"""Deque의 뒤에 값을 추가"""
self.list.add_at_index(self.size, value)
def remove_last(self):
"""Deque의 뒤에서 값을 제거"""
if self.list.size == 0:
return None # Deque가 비어 있으면 None 반환
return self.list.remove_at_index(self.size - 1)
def is_empty(self):
"""Deque가 비어 있는지 확인"""
return self.list.size == 0#import 생략
deque = MyDeque()
print("===== addFirst =====")
print(f"isEmpty: {deque.is_empty()}")
deque.add_first(1)
deque.add_first(2)
deque.add_first(3)
deque.add_first(4)
deque.add_first(5)
deque.print_all()
print(f"isEmpty: {deque.is_empty()}")
print()
print("===== removeFirst =====")
deque.remove_first()
deque.print_all()
deque.remove_first()
deque.print_all()
deque.remove_first()
deque.print_all()
deque.remove_first()
deque.print_all()
deque.remove_first()
deque.print_all()
print(f"isEmpty: {deque.is_empty()}")
print()
print("===== addLast =====")
deque.add_last(1)
deque.add_last(2)
deque.add_last(3)
deque.add_last(4)
deque.add_last(5)
deque.print_all()
print(f"isEmpty: {deque.is_empty()}")
print()
print("===== removeLast =====")
deque.remove_last()
deque.print_all()
deque.remove_last()
deque.print_all()
deque.remove_last()
deque.print_all()
deque.remove_last()
deque.print_all()
deque.remove_last()
deque.print_all()
print(f"isEmpty: {deque.is_empty()}")결과
===== addFirst =====
isEmpty: true
[5, 4, 3, 2, 1]
isEmpty: false
===== removeFirst =====
[4, 3, 2, 1]
[3, 2, 1]
[2, 1]
[1]
[]
isEmpty: true
===== addLast =====
[1, 2, 3, 4, 5]
isEmpty: false
===== removeLast =====
[1, 2, 3, 4]
[1, 2, 3]
[1, 2]
[1]
[]
isEmpty: true