[자료구조] 스택(Stack)이란?

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. 관련 문제

프로그래머스 문제 - [1단계] 같은 숫자는 싫어

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)

 

---

[참조문서 / 자료]

열혈강의 자료구조 - 이상진

[자료구조] | 스택(Stack)