FILO(First In Last Out)
- 먼저 들어간 것이 마지막에 나오는 규칙 = 선입후출
- 이때, 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.
동작 원리
- 초기에 빈 스택이 존재
- 데이터 1 push > (아래) 1 (위)
- 데이터 2 push > (아래) 1 2 (위)
- pop을 하면? > (아래) 1 (위), 맨 위에 있던 2가 빠져나옴
- 데이터 3 push > (아래) 1 3 (위)
- pop을 연속 2번 하면? > (아래) 1 3 (위), 맨 위에 있던 3부터 '3', '1' 순서로 빠져나옴
스택의 ADT(Abstract data type)
- ADT란? 우리말로 추상 자료형이다. 인터페이스만 있고 실제로 구현은 되지 않은 자료형
- 자바는 컬렉션 프레임워크에서 Stack 클래스를 제공하기 때문에 클래스의 객체를 생성해서 사용하면 된다.
- 참고) 덱 deque은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로도 사용할 수 있고, 큐로도 사용할 수 있다. Deque의 상위는 Queue이다. 구현체로는 ArrayDeque, LinkedList 등이 있다.
push, pop, isFull, isEmpty
- boolean isFull() : 스택에 들어있는 데이터 개수가 maxsize인지 확인하여 boolean값을 반환한다. 가득차 있다면 true
- boolean isEmpty() : 스택에 들어있는 데이터가 하나도 없는지 확인해 boolean값을 반환한다. 데이터가 없다면 true
- push(Item Type item): 스택에 데이터를 푸시
- Item Type item pop()
- int top(): 최근에 푸시한 데이터의 위치를 기록 (만약 top이 0이면 인덱스 번호가 0번인 데이터가 있다는 의미이므로, 아무것도 없으면 -1)
당연히 어떤 문제도 '스택으로 풀어라'라고 알려주지 않는다.
하지만 스택의 세부 동작을 충분히 안다면, 이 문제는 스택으로 풀어야겠다는 생각이 떠오를 수 있다.
자료구조의 세부 동작을 이해하면, 코테와 면접에 도움이 되니 성능과 특성을 잘 공부할 수 있도록 하자.
push 세부 동작
- push(3)을 호출하면, 내부적으로 isFull()을 수행하여 우선 data 배열에 데이터가 가득 찼는지 확인한다.
- 가득 차지 않았다면, top을 1만큼 증가시킨다.(데이터가 아무것도 없었다면 top은 -1인 상태임, 여기서 데이터가 들어오면 0으로 증가)
- 이후 top이 가리키는 위치 > data[0]에 3을 추가한다.
pop 세부 동작
- pop()을 호출하면, 내부적으로 isEmpty()을 우선 수행하여 data 배열에 데이터가 있는지 없는지 확인한다.
- 데이터가 있다면 top을 1만큼 감소시킨다. (0 -1 = -1이 된다. 즉 스택은 비어있는 상태가 됨)
- 이후 데이터 '3'을 반환한다.
Stack 클래스 사용
- 데이터를 그냥 저장하고, 순서와 상관 없이 임의 접근하기만 해도 되면 배열을 사용 하면 된다. 하지만, 최근에 삽입한 데이터를 대상으로 뭔가 연산을 해야한다면 스택이 떠올라야 한다.
Stack<Integer> stack = new Stack(); // 스택 객체 생성
// 스택에 데이터 푸시
stack.push(1);
stack.push(3);
// 스택이 비어 있는지 확인
Sytstem.out.println(stack.isEmpty()); // false
Sytstem.out.println(stack.pop()); // 3
Sytstem.out.println(stack.pop()); // 1
Sytstem.out.println(stack.isEmpty()); // true
- 자바의 Stack 클래스는 크기를 동적으로 관리하기 때문에 max_size나 isFull() 메서드는 없다. size()메서드로 스택에 들어있는 데이터의 수를 알 수는 있다.
- 또한 데이터를 꺼내지 않고 반환만 하는 peek() 메서드도 있다.