[자료구조] 스택 Stack

스택 (Stack)

  스택은 LIFO(Last-In First-Out)를 따르는 자료구조이다. 즉, 가장 최근에 넣은 아이템이 가장 먼저 제거되며 입구와 출구가 한 쪽만 열려있다고 생각하면 된다.

 

스택의 연산

(1) push( ) : 스택에 새로운 아이템을 추가한다. (가장 윗부분)

(2) pop( ) : 스택의 가장 위에 있는 항목을 제거하고 반환한다.

(3) isEmpty( ) : 스택이 텅 비어있는지 여부를 알려준다.

(4) peek( ) 혹은 top( ) : 스택의 가장 위에 있는 항목을 보여준다.

 

스택의 성능

- 탐색 : 스택에서 탐색은 모든 아이템을 하나하나 훑어봐야 되기 때문에 O(n)시간이 필요하다.

- 삽입 : 마지막에 데이터를 하나 추가해주면 되기 때문에 상수 시간에 가능하다.

- 제거 : 마지막 데이터를 하나 삭제해주면 되기 때문에 상수 시간에 가능하다.

 

스택의 활용 사례

(1) 웹 브라우저의 방문 기록

(2) 실행 취소 (undo)

(3) 계산기

(4) 수식의 괄호 검사 (parenthesis check)  - 실제로 계산기와 함께 스택 구현을 연습하는 예제로 많이 활용한다.

(5) 재귀 알고리즘

(6) 메모리의 스택 영역, 자바스크립트의 콜 스택, 실행 컨텍스트 스택 등