리스트와 스택의 차이

Category:

리스트와 스택의 차이점

어떤 자료구조를 사용할 것인지 APP을 통해 예시를 생각해보기

 

1. 리스트와 스택의 차이점

리스트는 아이템들의 사이에 뭔가 끼워 넣을 수 있다. 하지만 그 index에는 접근할 수 없다.

스택은 아이템들의 사이에 뭔가 끼워넣기가 어렵다. 즉 stack으로 존재하는 자료구조를 scope 하려면 전부 다 뽑아내야 한다.

 

2. 어떤 자료구조를 사용할 것인지 APP을 통해 예시를 생각해보기

 

<Bracket string문제>

왜 스택으로 풀어야 할까?

 

스택은 순서가 존재하며, 서로 상충(balance)하여 소거될 수 있는 자료형의 buffer로써 기능할 수 있다.

 

그렇다면 왜 하필 스택일까? 리스트는 안될까?

 

리스트로 이 문제를 풀었다고 생각해보면, 먼저 Top이라는 메소드를 구현해야 하고, push라는 메소드도 구현해야 한다.

 

즉 스택으로 푼다면 쉽게 풀릴 것을 돌아가는 것이다.

 

따라서 "순서"가 존재하고, "소거"가 가능한 자료형에는 스택이 어울린다.