728x90
📌 스택(Stack)
큐와 마찬가지로 컴퓨터 과학 분야의 주요 자료 구조 중 한가지로, 마지막에 넣은 데이터가 제일 처음에 나오는 LIFO(Last In, First Out)구조로 저장하는 형식을 말한다.
스택도 큐와 마찬가지로 프로그래밍에서 가장 많이 쓰는 자료구조 중 하나이다. LIFO(Last-In, First-Out) 구조 혹은 FILO(First-In, Last-Out) 구조라고도 한다. 스택의 대표적인 예 중 하나로 프링글스 과자를 예로 들 수 있다. 생산 과정에서 제일 먼저 들어간 감자칩은 제일 마지막에 꺼낼 수 있다.
✔️ 스택의 용어
| 용어 | 뜻 | 비유 | 자바 |
| Push(입력) | 스택에 데이터 입력 | 프링글스를 먹지 않고 도로 통에 넣기(?) | push(value), add(value), set(index, value), |
| Pop(삭제, 출력) | 스택의 데이터 출력 | 프링글스를 위에서부터 하나씩 먹기 | pop(), remove(), clear() |
| Top(위치) | 스택의 제일 윗 부분 (데이터가 두개 이상부터 분리) |
프링글스의 첫번째 감자칩 | - |
| Bottom(위치) | 스택의 제일 아래 부분 (데이터가 두개 이상부터 분리) |
프링글스의 마지막 감자칩 | - |
| Peek(확인) | 스택의 제일 윗 부분을 확인 | 제일 위에 감자칩이 있나 없나 확인..(?) | peek(), elementAt(Index), indexOf(value), contains(value), empty() |
✔️ 스택의 장단점
장점
- 구조가 단순해서 구현하기가 쉽다.
- 가장 위의 데이터만 확인하기 때문에 데이터의 저장/읽기 속도가 빠르다.
단점
- 데이터의 최대 개수를 미리 정해야 한다.
- 저장 공간의 낭비가 발생될 수 있다.(최대 개수를 너무 크게 설정했을 경우)
- 충분한 스택 공간을 확보하지 않으면 스택 오버플로우(Stack Overflow)가 발생한다.
✔️ 스택의 활용
스택의 특징인 후입선출(LIFO)은 여러 분야에서 활용되고 있다.
- 웹 브라우저 (뒤로가기, 앞으로가기)
- 실행 취소 (Undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 함수의 호출 : 기본적으로 모든 함수는 호출되는 순간 스택에 그 함수를 위한 영역이 할당된다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사
- 후위표기법 계산(AB+)
✔️ 스택의 간단한 구현
import java.util.*;
public class ImplStack<T> {
private ArrayList<T> stack = new ArrayList<T>();
public void push(T element) {
stack.add(element);
}
public T pop() {
if (stack.isEmpty()) {
return null;
}
return stack.remove(stack.size() - 1);
}
public boolean isEmpty() {
return stack.isEmpty();
}
public static void main(String[] args) {
ImplStack<Integer> implStack = new ImplStack<Integer>();
implStack.push(1);
implStack.push(2);
System.out.println(implStack.pop());
implStack.push(3);
System.out.println(implStack.pop());
System.out.println(implStack.pop());
}
}
댓글