[Data Structure] 스택에 대해 간단하게 설명하기

CS 이론 관련 면접 준비를 위해 랜덤으로 떠오르는 것에 대해 말해보는 연습을 하고 있다

 

스택은 후입 선출의 선형 자료구조이다. pop 작업은 스택의 최상단 top에서만 수행할 수 있고 가득찬 스택에 더 넣으려고 하면 stack overflow, 비어있는 스택에서 값을 추출하려고 하면 stack underflow가 발생한다. 

 

자바에서는 stack 클래스를 사용할 수 있으나 stack 클래스 자체는 내부적으로 vector 를 상속받기 때문에 인덱스를 통한 접근이나 수정이 가능하기는 하다. 그래서 후입선출이라는 stack 특성에 위반되는 코드를 작성할 우려가 있으므로 deque 인터페이스 구현체를 사용하는 것을 더 권장한다. 

 

vector 에 포함된 메소드들은 synchronized 방식으로 구현되어 있어서 멀티 스레드 환경에서 동기화된다는 장점이 있지만 단일 스레드에서는 동기화가 일어나는 것이 불필요한 낭비이므로 성능에 악영향을 줄 수 있다. 

 

하지만 deque 인터페이스는 후입선출 특성을 그대로 가지고 가면서 synchronized 여부에 맞게 각각의 구현체를 택할 수 있다는 점이 성능 최적화에 유리하다. 

 

(deque는 queue를 확장한 것으로 입출력을 양끝에서 할 수 있고 인덱스로 요소에 접근하거나 수정할 수 없도록 한다.)

 

(동기화 관련하여 ... stack은 모든 작업에 lock이 사용되기 때문에 synchronized 방식의 구현임을 알 수 있는 것이다.)

 

(stack은 vector를 상속받은 상태이므로 다중 상속을 지원할 수 없다.)