자바의 자료구조 - Stack

순서가 좀 이상해진 기분이 들지만 이번 자료구조는 Stack이다.

 

스택은 총의 탄창을 생각해보면 구조가 매우 흡사하다.

탄창을 입구로 총알을 넣고, 가장 먼저 넣은 총알이 가장 마지막에 발사되게 된다.

 

이러한 선입후출의 자료구조가 Stack이다. ( First In Last Out )

 

단순한 구조이기 때문에 Stack이 갖는 특징이 있는데,

 

     1. 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
     2. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
     3. 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

 

 

 : 스택의 사용

 : 재귀 알고리즘

     재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
     재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
     스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
     또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
 : 웹 브라우저 방문기록 (뒤로가기)
 : 실행 취소 (undo)
 : 역순 문자열 만들기
 : 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
     Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
 : 후위 표기법 계산

 

 

 : 메소드

     pop() : 스택에서 가장 위에 있는 항목을 제거, 배출
     push(item) : item 하나를 스택의 가장 윗 부분에 추가
     peek() : 스택의 가장 위에 있는 항목을 반환
     isEmpty() : 스택이 비어 있으면 true, 비어있지 않으면 false 반환

     search(Object o) : 해당 Object의 위치를 반환, top의 위치는 1 없을경우 -1 반환

     ( 위치는 top 부터 선입된 것으로 1,2,3,,,, )