지난 포스팅에서 built-in data structure를 알아보았고, 이번 포스팅에서는 추상 데이터 타입(Abstarct data type)으로 분류되는 자료구조에 대해 포스팅할 것이다.
Stack은 배열의 끝에서만 데이터에 접근할 수 있는 선형 자료구조를 뜻한다.
인덱스 접근이 제한되며 후입선출(LIFO, Last-In & First-Out) 구조이다.
파이썬에서 자체적으로 Stack module을 제공해주지 않기 때문에 외부 모듈을 다운받아 사용하거나, 제차적으로 class만들 수도 있고, list의 내장 method를 사용해 구현할 수 있다.
- push
- pop
- peek(또는 top)
- empty
- size
Stack은 위 다섯가지의 동작(method)들을 가지고 있으며 시간복잡도는 다섯개 모두 O(1)이다.
push는 stack 맨 끝에 item(항목)을 삽입한다.
class Stack:
def push(self, value):
self.items.append(value)
pop은 stack 맨 끝의 항목(item)을 반환(return)하며 동시에 stack에서 제거한다.
class Stack:
def pop(self):
return self.items.pop()
peek는 맨 끝의 항목을 조회한다는 점에서 pop과는 차이점이 있다.
class Stack:
def peek(self):
if self.is_empty():
return print("Empty Stack")
else:
return self.items[-1]
empty는 stack이 비어있는지 조회하는 method로 boolean값(Ture
/False
)을 반환한다.
class Stack:
def is_empty(self): # restful convention에 맞춰 동사(verb)형태로 작성한다.
return not bool(self.items)
size는 스택의 크기(항목의 갯수)를 확인한다.
class Stack():
def size(self):
return len(self.items)
모든 코드를 하나로 합쳐보면 다음과 같다.
class Stack:
def __init__(self) -> None:
self.items = []
def size(self) -> int:
return len(self.items)
def is_empty(self) -> bool:
return not bool(self.items)
def push(self, value) -> None:
self.items.append(value)
def pop(self):
if self.is_empty():
print("Empty Stack")
else:
return self.items.pop()
def peek(self):
if self.is_empty():
return print("Empty Stack")
else:
return self.items[-1]
def __repr__(self):
return repr(self.items)
스택은 깊이 우선 탐색(DFS)에서 사용된다.
Queue는 Stack과 다르게 선입 선출(FIFO, First-In & First-Out)구조로 배열에 들어온 순서대로 접근하는 선형 자료구조를 뜻한다. 그리고 Stack과 다르게 python에서 제공해주는 Queue module이 있다.
Queue와 Stack의 공통점은 인덱스 접근이 제한되는 것이다.
from queue import Queue
queue = Queue()
- enqueue
- dequeue
- peek(또는 front)
- empty
- size
Queue method 중 enqueue는 list의 insert method를 사용해 구현해 시간복잡도가 O(n)이라는 단점이 있다. 하지만 Queue module을 사용할 경우 이러한 단점이 없어지게 된다.
enqueue는 queue 맨 끝에 item을 삽입한다.
python queue 모듈에서는 append
method를 사용하지만 dequeue 방법의 차이가 있다.
class Queue:
def enqueue(self, item) -> None:
self.items.insert(0, item)
dequeue는 queue 맨 앞의 item을 반환하고 제거한다.
class Queue:
def dequeue(self):
if self.is_empty():
return self.items.pop()
else:
print("Empty Queue")
peek는 stack과 동일하게 queue 맨 앞의 항목을 조회한다.
class Queue:
def peek(self):
if self.is_empty():
return self.items[-1]
else:
print("Empty Queue")
empty는 stack과 동일하게 queue가 비어있는지 조회하는 method로 boolean값(Ture
/False
)을 반환한다.
class Queue:
def is_empty(self):
return not bool(self.items)
size는 stack과 동일하게 queue의 크기(항목의 갯수)를 확인한다.
class Queue:
def size(self):
return len(self.items)
모든 코드를 하나로 합치면 다음과 같다.
class Queue:
def __init__(self) -> None:
self.items = []
def is_empty(self):
return not bool(self.items)
def enqueue(self, item) -> None:
self.items.insert(0, item)
def dequeue(self):
if self.is_empty():
print("Empty Queue")
else:
return self.items.pop()
def peek(self):
if self.is_empty():
print("Empty Queue")
else:
return self.items[-1]
def size(self) -> int:
return len(self.items)
def __repr__(self) -> str:
return repr(self.items)
큐는 너비 우선 탐색(BFS)에서 사용된다.