[Java] Stack (스택)

Stack?

위처럼 접시를 쌓으면 마지막에 쌓은 접시가 맨 위에 놓일 것이다. 그러면 당연하게도 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다.

 

Stack도 이와 같은 방식으로 동작한다.

 

이처럼 마지막에 쌓은 것을 가장 먼저 꺼내게되는 것을 후입선출(Last In First Out, LIFO)이라고 한다.

Stack의 주요 연산 Push와 Pop

• push(): 요소를 추가
• pop(): 가장 최근에 추가된 요소를 제거

Stack의 시간복잡도

• push(): O(1)
• pop(): O(1)
• get(): O(n)

get(): 값을 조회하는 메소드

 

Appendix

 

1946년 앨런 튜링은 서브 루틴을 호출하는 과정을 bury, 되돌아오는 과정을 unbury라고 불렀는데 이것을 스택의 기원이라고도 한다. 스택은 콜 스택(call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다. 

 

컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로우(Stack Buffer Overflow)라고 부른다. stackoverflow.com이 여기에서 유래되었다.

 

• [Java] Stack 정리