-
[자료구조] 스택(Stack)이란?자료구조 2024. 2. 26. 02:06
1.스택(Stack)이란?
스택(Stack)은 자료를 한 방향으로만 쌓는,
후입선출(Last-In-First-Out) 형태 선형 자료 구조이다.처음과 중간, 그리고 끝에 자료를 추가할 수 있는 리스트와 다르게 스택은 오직 스택의 제일 위에서만 자료를 추가하고 추출할 수 있다.
a) push(item)
새로운 자료를 스택에 추가하는 것을 푸시(push)라고 한다.
위 그림은 A와 B가 스택에 추가되는, 즉 푸쉬하는 과정을 보여주고 있다. 제일 먼저 A가 빈 스택에 추가된다, 그 다음 단계로 저장된 A의 위쪽으로 새로운 자료 B가 저장된다.
푸쉬를 통해 스택에 새로운 자료를 추가할 경우, 새로운 자료는 항상 기존 자료의 위쪽으로마 저장됨을 알 수 있다.
즉, 푸쉬는 스택의 맨 위에 새로운 자료를 추가한다.
b) pop()
스택에서 자료를 꺼내는 것을 팝(pop)이라고 한다.
팝 연산은 스택에서 가장 최신 해당 자료를 제거하고 이를 반환한다. 최상위 자료를 반환하는 팝 연산 때문에 스택에 자료를 추가한 순서와 역순으로 자료가 반환된다. 위의 예에서는 자료가 C -> B -> A 순으로 반환된다.
b) peek()
자료를 제거하거나 추가하지 않고 해당 자료에 접근만 하는 것을 피크(peek)라고 한다.
단, 이 경우에도 스택의 가장 최상위에 있는 자료에만 접근을 할 수 있다.
2. 언제 주로 사용하는가?
- 스택을 활용하면 "재귀함수"를 필요로하는 소스코드에 "재귀함수"를 사용하지 않고 구현할 수 있다.
- 웹 브라우저의 방문기록에서도 스택의 특징을 활용하여 "뒤로가기"를 구현할 수 있다.
- 프로그램의 실행취소(Undo)에서 활용된다.
3. 주의 할 점
스택에 아무 자료가 저장되지 않은 상태를 공백 상태라고 하는데, 공백상태일 때 팝 연산이 호출되면 부족(Underflow)현상이 발생한다.
반대로 스택의 크기보다 더 큰 자료를 스택에 추가하려고 할 때, 자료가 추가할 수 없는 현상인 넘침(overflow)현상이 발생한다.
4. 시간 복잡도
스택의 삽입이나 삭제시 맨 위의 데이터를 삭제하기 때문에 시간복잡도는 늘 O(1) 이다. 하지만 특정 데이터를 찾을때는 데이터를 찾을때까지 순차적으로 수행해야 하므로 O(n) 시간복잡도를 갖는다.
5. 관련 문제
def solution(arr): answer = [] answer.append(arr[0]) #배열의 첫번째 자료 answer에 추가(stack에 추가) for i in range(1,len(arr)): if answer[-1] != arr[i]: #peek()한 값과 동일하지 않은지 비교 answer.append(arr[i]) return answer
def add_num(a, b): a = a[::-1] b = b[::-1] # 결과를 저장할 변수 result = [] carry = 0 # 올림값을 저장할 변수 # 두 숫자 중 더 긴 길이를 찾기 max_length = max(len(a), len(b)) # 각 자릿수별로 덧셈을 수행 for i in range(max_length): # 각 자릿수에 해당하는 값가져옴, 없을 때 0 if i < len(a): a_digit = int(a[i]) else: a_digit = 0 if i < len(b): b_digit = int(b[i]) else: b_digit = 0 # 현재 자릿수에 대한 덧셈을 수행 digit_sum = a_digit + b_digit + carry result.append(str(digit_sum % 10)) # 현재 자릿수의 결과를 결과 리스트에 추가 carry = digit_sum // 10 # 올림값 갱신 # 마지막 올림값이 있는 경우 if carry: result.append(str(carry)) result = ''.join(result[::-1]) return result # 입력 받기 - 공백 제거 a = input().strip() b = input().strip() # 큰 수 덧셈 수행 result = add_num(a, b) # 결과 출력 print(result)
[참조문서 / 자료]
열혈강의 자료구조 - 이상진
'자료구조' 카테고리의 다른 글
[자료구조] Queue 알아보기 (0) 2024.03.04