Koo's.Co

파이썬에서 제공하는 리스트를 사용하면 스택의 기능을 모두 사용할 수 있다. push연산은 append, pop연산은 그대로 pop을 이용하면 된다. 여기서는 노드를 이용해 스택을 구현해보려 한다. 구현하려는 스택의 추상 데이터 타입은 다음과 같다. empty() : 비었다면 True를, 아닐 경우 False를 반환 push(item) : 스택에 item을 삽입 pop() : 스택에 마지막으로 들어온 item을 반환, 스택이 비어있는 경우 False를 반환 peek() : 스택에 마지막으로 들어온 item을 반환 __len__() : 스택에 크기를 반환 1. 노드 class Node(object): def __init__(self, item, pointer): self.item = item self.poi..

스택이란? 스택은 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 선형 자료구조이다. 나중에 들어온 원소가 제일 먼저 나가는 후입선출(LIFO: Last In First Out) 구조를 갖는다. 책을 상자 안에 쌓아서 넣을 때, 나중에 쌓은 책을 먼저 빼는 모양을 생각할 수 있다. 스택 안에 원소를 집어넣는 push연산, 삽입된 원소를 빼내는 pop연산, 제일 위에 있는 원소값을 반환하는 peek연산을 갖는다. 컴퓨터 내부에서 프로그램에 대한 정보를 저장하는 자료구조에도 쓰이는 등 컴퓨터 내부에서도 많이 사용된다. 간단하게 구현가능하면서도 여러 상황에 응용할 수 있어 많이 쓰이는데 힙 영역에 데이터를 저장하거나 재귀함수를 호출하는 과정도 스택 형태로 사용된다.