Stack
쉽게 원형 통을 생각하면된다. 원형통에 어떤 물체를 넣게 되면, 제일 위에 있는 물체부터 차례대로 꺼내야 제일 바닥에 있던 물체를 꺼낼 수 있다.
이를 LIFO(Last in First Out) 후입선출 구조 라고 한다.
주요 메서드
- push 데이터 삽입
- pop 마지막에 삽입했던 데이터 삭제 (stack 비어있지 않을때만)
- top 마지막에 삽입했던 데이터 return만 해줌 (보기만 하는 것)
- isEmpty 현재 스택이 비어있는지 확인
파이선에서 리스트를 그냥 사용해 스택처럼 사용해도 되지만, list로 구현했다.
class Stack():
def __init__(self):
self.stack=[]
def push(self,data):
self.stack.append(data)
def pop(self):
if self.isEmpty():
print("Error Stack is Empty")
return None
popped_object=self.stack.pop()
return popped_object
def isEmpty(self):
is_empty=False
if len(self.stack)<=0:
is_empty=True
return is_empty
def top(self):
top_object=None
if self.isEmpty():
print(top_object)
else:
top_object=self.stack[-1]
return top_object
이 자료구조는 그래프 탐색 알고리즘 중 하나인 DFS 등 다양한 곳에 사용되는 자료구조이니 확실히 알아두자!
Queue
스택과 반대로 Qeueu는 먼저 들어간 입력값이 먼저 나오는 FIFO(First In First Out) 구조를 가지고 있다. 쉽게 은행창구를 생각하면 된다. 먼저 번호표를 뽑는 사람이 먼저 창구를 갈 수 있는 선입선출 구조이다.
주요 메서드
- enqueue: rear가 가리키는 위치에 원소를 삽입한다.
- dequeue: front가 가리키는 위치에 있는 원소를 삭제한다.
- peek: 가장 첫번째에 있는 원소를 삭제하지 않고 반환한다.
파이선에서는 list,deque(double_ended_queue)를 활용해서 구현가능하다.
deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조다. popleft()를 통해 첫번째 데이터를 삭제할 수 있다. list에서 pop()과 같다.
list) 큰 인덱스 방향으로 enqueue 하는 방법
# list
queue=[4,5,6]
queue.append(5)
queue.append(7)
# >> queue=[4,5,6,5,7]
queue.pop(0)
queue.pop(0)
# >> queue=[6,5,7]
list) 작은 인덱스 방향으로 enqueue 하는 방법
# list
queue=[4,5,6]
queue.insert(0,5)
queue.insert(0,7)
# >> queue=[7,5,4,5,6]
queue.pop()
queue.pop()
# >> queue=[7,5,4]
deque) 큰 인덱스 방향으로 enqueue 하는 방법
#deque
from collections import deque
queue=deque([4,5,6])
queue.append(5)
queue.append(7)
# >> queue=[4,5,6,5,7]
queue.popleft()
queue.popleft()
# >> queue=[6,5,7]
deque) 작은 인덱스 방향으로 enqueue 하는 방법
#deque
from collections import deque
queue=deque([4,5,6])
queue.appendleft(5)
queue.appendleft(7)
# >> queue=[7,5,4,5,6]
queue.pop()
queue.pop()
# >> queue=[7,5,4]
Queue도 BFS알고리즘 등 다양한 곳에 사용되는 자료구조이다.
Reference
(●'◡'●)