스택

스택 (Stack)

한쪽 끝에서만 접근이 가능한 후입 선출(LIFO : Last-In-First-Out) 형식으로 입출력이 이루어지는 자료구조이다.

예로는 쌓여있는 식당의 접시, 창고의 상자 등이 있다.

추상 자료형

create() /* 스택을 생성 */
is_empty(s) /* 스택이 비어있는지 검사 */
is_full(s) /* 스택이 가득차있는지 검사 */
push(s, e) /* 스택의 맨 위 요소 e를 추가 */
pop(s) /* 스택의 맨 위 요소를 삭제 */
peek(s) /* 스택의 맨 위 요소를 반환 */

구현

• 배열로 구현한 스택
• 연결 리스트로 구현한 스택

예시

• 괄호 검사
• 수식의 계산
• 미로 탐색 문제