[Java / 자료구조] 스택 (Stack) 정리

스택(Stack)이란?

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조이다. 다시 말해 가장 먼저 들어간 데이터는 가장 나중에 나올 수 있고 마지막에 들어간 데이터가 가장 먼저 나올 수 있는 구조이다.

 

스택의 사용 사례

• 음료수 진열대 (먼저 들어간 것이 나중에 나옴)
• 인터넷 브라우저 창 (뒤로 가기, 앞으로 가기 기능)

 

스택의 특징

• 입력과 출력이 하나의 방향으로 이루어지는 제한적인 접근에 있다. 
• LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.
• 데이터는 하나씩 넣고 뺄 수 있다.

 

스택 클래스 메서드

empty()

해당 스택이 비어 있는지 확인한다. boolean 타입을 리턴한다.

 

peek()

해당 스택의 제일 상단에 있는(제일 마지막에 저장된) 요소를 반환한다. 

 

pop()

해당 스택의 제일 상단에 있는 요소를 반환하고, 해당 요소를 스택에서 제거한다.

 

push(E item)

해당 스택의 제일 상단에 전달된 요소를 삽입한다.

 

search(Object o) 

해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환한다. int 타입을 리턴한다.

이때 인덱스는 제일 상단에 있는 요소의 위치부터 0이 아닌 1부터 시작한다.

// search()

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.search(1));
System.out.println(stack.search("hello"));

/* 출력
3
-1
*/

search(1)은 1이라는 데이터가 stack에 있는지를 찾아서 인덱스 3으로 반환했다. 가장 먼저 삽입된 데이터 1이 마지막 인덱스 3을 갖게 된 것이다. Stack에 없는 데이터인 hello에 대한 결과는 -1을 반환했다.

 

LIFO(Last In First Out)

Ex1. 1, 2, 3, 4를 스택에 차례대로 넣는다.

Stack<Integer> stack = new Stack<>(); // Integer형 스택 선언

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.

Ex2. 스택이 빌 때까지 데이터를 전부 빼낸다.

stack.pop();
stack.pop();
stack.pop();
stack.pop();
---------------------------

---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 된다.