스택은 가장 나중에 넣은 원소를 먼저 꺼내는 후입선출 자료구조이다. 보통 push, pop과 꼭대기 원소 확인 연산을 제공한다.
원리
한쪽 끝에서만 삽입과 제거를 수행한다. 배열이나 연결 리스트로 구현할 수 있으며, 인터페이스의 순서 규칙과 실제 저장 방식은 별개이다.
예시
여는 괄호를 만나면 쌓고 닫는 괄호를 만나면 짝이 맞는지 확인하며 꺼낸다. 입력 처리가 끝난 뒤 스택이 비어 있어야 모든 괄호가 닫힌 것이다.
주의할 점
빈 스택에서 꺼내는 경우를 처리해야 한다. 실행 중 함수 호출을 관리하는 호출 스택과 추상 자료구조 스택은 관련이 있지만 같은 구현을 뜻하지 않는다.