[JAVA] 자료구조 - 스택(1)

스택

 

스택에 대해 알아보겠다.

 

스택이란 쉽게 생각해서 상자 쌓기 라고 보면 된다.

 

가장 처음 쌓은 것이 제일 마지막에 나가게 되고, 가장 마지막에 쌓은 것이 제일 먼저 나가게 된다.

 

스택도 마찬가지고 이것을 후입선출 이라고 한다.  (후입선출, LIFO : Last - In - First - Out)

 

스택의 입출력은 스택의 맨 위 인덱스에서만 일어나고 중간에서는 데이터가 삭제, 삽입 될 수 없다.

 

---

스택의 기본연산

스택의 기본연산 에는 삽입연산과 삭제연산이 있다.

 

push : 삽입 연산

pop : 삭제 연산

 

push(DATA) 를 했을 때, 비어 있는 스택에 DATA가 삽입된다.

다시 push(DATA2)를 하면, DATA 위에 DATA2 가 쌓이게 된다.

스택이 가득 차게 된다면 push 연산은 수행 될 수 없으며 오류를 반환하게 된다.

따라서 push 연산을 수행하기 전 is_full 함수가 선행되어 스택이 포화상태인지 확인해야 한다.

 

pop 연산이 수행되면 가장 위에 있는 DATA2가 삭제된다.

만약 pop 연산을 할 데이터가 없어서 출력이 불가능하다면 역시 오류를 반환한다.

마찬가지로 pop 연산을 수행하기 전 is_empty 함수가 선행되어 스택이 공백 상태인지 확인을 해야한다.

---

스택의 상태 검사 함수

 

is_empty ( ) : 스택이 공백상태인지 검사

is_full ( ) : 스택이 포화상태인지 검사

create ( ) : 스택 생성

peek ( ) : 스택의 요소들을 삭제하지 않고 조회 (pop은 요소를 완전히 삭제하며 가져옴)

---

스택을 구현하는 방법

 

스택을 구현하는 방법에는 배열과 연결리스트가 있다.

배열을 이용하는 방법은 간단하고 성능이 우수한 반면 스택의 크기가 고정되는 약점이 있다.

연결리스트를 이용하는 방법은 구현이 약간 복잡한 대신 스택의 크기를 필요에 따라 가변적으로 할 수 있다.

 

다음 포스팅에는 스택을 배열로 구현한 괄호 검사 프로그램에 대해 포스팅 하겠다.