cs/알고리즘
자료구조-stack
ssoonn
2024. 6. 30. 22:58
스택의 정의
한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO, Last In First Out) 형태의 선형 자료구조
Stack 클래스는 내부에서 최상위 배열인 Object[] 배열을 사용해 데이터를 관리한다.
스택의 구조
- 상단(stack top) : 스택에서 입출력이 이루어지는 부분
- 하단(stack bottom): 반대쪽 바닥 부분
- 요소(element): 스택에 저장되는 것
- 공백 스택(empty stack): 공백 상태의 스택
- 포화 스택(full stack): 포화 상태의 스택 (풀스택)
제공 연산
- pop()
- 가장 위의 항목 제거
- push(item)
- item 하나를 스택 가장 위에 추가
- peek()
- 스택 가장 위 항목을 반환
- isEmpty()
- 스택이 비어있을 때 true 반환
- isFull()
- 스택이 차있을 때 true 반환
데이터 입력: push()
스택에 데이터를 추가할 땐 push()를 사용한다.
데이터 추가 시 최상단에 추가하며, 인덱스를 증가하며 이루어진다.
데이터 삭제: pop()
스택에 데이터 삭제 시 pop()을 사용한다.
최상단 데이터(가장 마지막에 추가된 데이터)를 삭제한다.
시간복잡도
스택의 삽입/삭제 시 맨 위의 데이터만을 삭제하기에, 시간복잡도는 늘 O(1)
특정 데이터를 찾는 경우, 데이터를 찾을 때까지 순차적으로 수행하므로 O(n)
스택 활용
- 괄호의 짝 검사
- 괄호의 짝, 괄호의 순서 검사
- 웹 브라우저 방문기록(뒤로가기)
- 역순 문자열 만들기
- 실행취소(undo)
- 수식의 괄호 검사
- 연산자 우선순위 표현을 위한 괄호검사
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야하는 경우, 임시 데이터를 스택에 넣음
- 재귀함수를 빠져나와 backtrack할 때 스택에 넣어둔 임시 데이터를 꺼냄
예제
https://www.acmicpc.net/problem/17608
(브론즈2 문제밖에 없어서 이걸로 했습니다)