Stack
Stack은 쌓여있는 팬케익을 위에서부터 먹는 것과 같은 개념이다. 세로로 쌓여있는 기둥처럼 나중에 들어온 자료가 먼저 나간다(읽힌다)고 해서 stack이라고 한다. (LIFO(Last In First Out))
Stack에 자료를 넣을 때는 push, 읽어들일 때는 pop을 쓴다. 다만 pop은 원 자료구조를 변경시키기 때문에 읽어들임과 동시에 stack에서 그 자료를 삭제한다.
리스트를 사용한 stack 구현 예제
class Stack:
# 빈 리스트 생성
def __init__(self):
self._stack = []
# push 메서드는 위에서 생성한 리스트에 자료를 맨 뒤에 밀어넣는다.
def push(self, data):
self._stack.append(data)
# pop 메서드는 리스트에 있는 것 중 가장 마지막 인덱스([-1])에 해당하는 자료를 찾고
# 그것을 삭제(del)한다.
# 만약 리스트가 비어있으면 None을 리턴한다.
def pop(self):
if len(self._stack) == 0:
return None
data = self._stack[-1]
del self._stack[-1]
return data
# peek 메서드는 가장 뒤에 있는 요소를 리턴한다.
# 만약 리스트가 비어있으면 None을 리턴한다.
def peek(self):
if len(self._stack) == 0:
return None
data = self._stack[-1]
return dataStack 사용 예시
- 웹 브라우저 뒤로 가기, 실행 취소
- 함수 호출 기록 저장 방식
Queue
Queue는 stack과 반대로 먼저 들어온 자료가 먼저 나간다. (FIFO(First In First Out))
리스트를 사용한 Queue 구현 예제
class Queue:
# 빈 리스트 생성
def __init__(self):
self._queue = []
# push 메서드는 위에서 생성한 리스트에 자료를 맨 뒤에 밀어넣는다.
def push(self, data):
return self._queue.append(data)
# pop 메서드는 가장 앞에 있는 자료를 삭제한다.
# 만약 리스트가 비어있으면 None을 리턴한다.
def pop(self)
if len(self._queue) == 0:
return None
return self._queue.pop()
# peek 메서드는 가장 앞에 있는 요소를 리턴한다.
# 만약 리스트가 비어있으면 None을 리턴한다.
def peek(self):
if len(self._queue) == 0:
return None
return self[0]Stack 자료구조 사용 예시
- 예약 시스템
- 프린터 인쇄 대기목록
- CPU 프로세스 스케줄링