ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [자료구조] 스택(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. 관련 문제

    프로그래머스 문제 - [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)

    '자료구조' 카테고리의 다른 글

    [자료구조] Queue 알아보기  (0) 2024.03.04