공돌이 공룡의 서재

0. 들어가기 전 2020/08/18 - [코딩/자료구조] - [Python] 자료구조: 스택(Stack) / LIFO [Python] 자료구조: 스택(Stack) / LIFO 1. 기본 개념 스택(Stack)이란 쌓아 올린다는 의미가 있다. 차곡차곡 쌓여있는 접시들을 생각해보자. 접시를 쌓을 때 위로 하나씩 올리고 뺄 때도 위에서부터 하나씩 뺀다. 중간에 있는 접시를 빼 mr-waguwagu.tistory.com 이번 포스트에서는 기본적인 개념에 대해서는 설명하지 않고, 간단한 예시를 통해 어떻게 쓰일 수 있는지를 정리하고자 한다. 스택구조가 어떻게 구현됐는지와 O(n)이 나오는지를 유의하며 보자. 1. 클래스 정의 class Stack: def __init__(self): self.box = [] d..

1. 기본 개념 스택(Stack)이란 쌓아 올린다는 의미가 있다. 차곡차곡 쌓여있는 접시들을 생각해보자. 접시를 쌓을 때 위로 하나씩 올리고 뺄 때도 위에서부터 하나씩 뺀다. 중간에 있는 접시를 빼면 무너지고 만다. 여기서 순서로 생각해보면 가장 마지막에 올린 접시가 뺄 때는 가장 먼저 나간다는 것을 알 수 있다. 이것을 LIFO(Last in, First out)이라고 한다. 또 다른 예시로 구멍이 하나인 통이 있다고 생각해보자. 빨강부터 보라색까지 무지개 색으로 7개의 마카롱이 있고 빨간색부터 통에 넣는다 생각하자. 마지막으로 들어가는 마카롱은 보라색인데, 꺼낼 때는 마지막으로 들어간 보라색 마카롱을 마카롱을 제일 먼저 꺼내고 제일 먼저 들어간 빨간 마카롱이 제일 마지막에 나온다. 이처럼 새로운 개체..