스택(stack)

stack의 정의

LIFO(Last In First Out) 형식의 자료구조

LIFO: 한 쪽 끝에서만 자료를 넣거나 빼는 것

시간 복잡도

삽입/삭제: O(1)

검색: O(n)

java에서의 stack

stack은 vector를 상속받으므로써 구현된다

push: 상속받은 vector에 존재하는 Object리스트에 값을 추가하는 메소드

pop: stack에서 가장 최근에 push한 값을 빼는 메소드

peek: stack에서 가장 위에 있는 값을 보여주는 메소드

이 외에는 serach(), empty()같은 메소드들이 존재한다.

여기서 주의깊게 봐야할 점은 pop(), peek(), search()에 모두 synchronized가 붙어있다는 것이다!

java에서 stack이 쓰이지 않는 이유? == vector가 쓰이지 않는 이유

stack이 상속하는 vector를 확인해보면, 우리가 왜 stack이 쓰이지 않는지 알 수 있다.

vector의 문제점

get()이나 set()이 사용되는 메소드 외에도 여러 메소드에 synchronized 키워드가 붙는다

이게 왜 문제일까?

• sychronized는 특정상황에서 성능이 저하되기 때문이다.
  • vector에 존재하는 다양한 메소드가 sychronized 키워드를 가지고 있기 때문에 메소드를 부를 때마다 lock을 한다. 한번으로 충분한 lock을 무분별하게 사용하기 때문에 비효율적일 뿐더러 시간적으로도 오버헤드가 존재하여 사용하지 않는 게 낫다.
  • 따라서, vector를 사용하기보다는 vector와 매우 비슷하지만, 빠른 arrayList를 사용하는 게 더 낫다고 한다.
  • 그리고 java에서 스택을 구현할 일이 필요하다면, 구현체를 deque로 설정하는 게 좋다.