스택의 개념
입력과 출력을 한 방향으로 제한한 알고리즘
- 바닥부터 데이터를 차곡 차곡 쌓는 개념
- 회전 초밥집에서 다 먹은 그릇을 쌓아 놓는 것처럼 데이터를 쌓아 놓는다는 의미
Push : 데이터를 쌓아 놓음
Pop : 데이터를 꺼냄
LIFO(Last In First Out)방식
- 나중에 들어온것이 첫번째로 나감
스택의 구현
def push(item):
stack.append(item)
def pop():
return stack.pop()
if __name__ == "__main__":
stack = []
push(1)
push(2)
push(3)
push(4)
print("현재 stack의 모습")
print(stack)
while stack:
print(f"POP > {pop()}")시간의 효율성
스택 알고리즘은 연결 리스트를 사용하기도 하지만 배열을 사용하여 구현하기도 함
스택의 개념 자체는 검색하는 과정이 필요 없이 가장 선두에 있는 데이터를 Pop
데이터를 삽입할 떄도 가장 선두에 집어 넣음
연결 리스트를 사용한다고 하더라도 시간적인 효율성 면에서 배열보다 나은 점이 없음
공간의 효율성
배열로 구현한 스택이 배열의 전체 크기에 국한된다는 점 때문에 연결 리스트를 사용한 스택이 더 효율적이라고 말할 수는 있음
대부분의 스택을 사용하는 경우에는 스택의 크기를 정해놓고서 사용하는 것이 일반적이기 때문에 스택을 배열로 구현 했다고 해서 공간의 효율성이 많이 저하된다고 보기 어려움
코드의 효율성
연결 리스트에 대한 코드를 이해할 수 있다면 이것을 이용해서 만든 스택의 코드는 쉽게 이해할 수 있음
연결 리스트를 이용한 스택이라고 하더라도 연결 리스트의 링크를 연결하거나 새로운 노드를 생성하는 정도의 코드
learn !