[항해99 취업 리부트 코스 학습일지] Day 13 - 알고리즘 : 스택, 큐, 덱

[학습 내용]

오늘은 알고리즘 및 자료구조의 입문 단계라고 할 수 있는 스택과 큐에 대해서 학습했다. 그중에서도 스택을 알아보자.

1. 스택(Stack)

스택은 '쌓는다' 라는 이름의 어원처럼, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 LIFO(Last In First Out)의 구조를 가진 자료구조이다. 일상 생활에서도 많이 볼 수 있는 형태인데, 곽티슈나 좁고 긴 바구니에 물건을 넣는다면 이런 구조를 지닐 것이다. 실제 프로그램 내부에서도 이런 구조를 지닌 대표적인 예는 우리가 함수를 형성하고 저장할 때, 함수가 메모리의 스택 영역에 실행 순서에 따라 차근차근 저장되고, 가장 나중에 호출된 함수부터 차례차례 해제된다. 이런 스택을 프로그램에서 차용하는 가장 큰 이유는 처음 실행했던 함수로 돌아가기 위함이다.
스택은 다음과 같은 연산 기능을 지닌다.

• push() : 스택에 데이터를 삽입한다.
• pop() : 최근에 푸시한 데이터를 빼내고, 그 값을 반환한다.
• isEmpty() : 스택에 데이터가 들어있지 않은지 확인한다.
• isFull() : 스택에 들어있는 데이터 개수가 최대치인지 확인한다.

위에서 설명한 연산의 과정을 크게 2가지로 나누면 다음과 같다.

• 데이터 3을 추가하기 위해 push(3)을 호출한다.
  • 먼저 IsFull()을 수행해 스택 내부의 공간이 있는지 확인한다.
  • 공간이 있다면 top을 1만큼 증가시킨 후 top이 가리키는 위치에 3을 추가한다.
• 데이터를 삭제하기 위해 pop()을 호출한다.
  • 먼저 isEmpty()를 수행해 내부적으로 데이터가 없는지 확인합니다.
  • 데이터가 있다면 top을 1만큼 감소시킨 후 top이 가리켰었던 값을 반환한다.

여기서 top은 가장 최근에 추가한 데이터의 위치를 참조하는 변수로 이해하면 된다.

파이썬에서는 stack을 별도로 구현하지 않고 동적 배열인 list를 활용해서 사용하지만, 다른 언어에서도 쓸 수 있기 때문에 기본적인 로직을 코드로 짜보자.

stack = []
max_size = 10  # 스택의 최대 크기


def isFull(stack):
    return len(stack) == max_size


def isEmpty(stack):
    return len(stack) == 0


def push(stack, item):
    if isFull(stack):
        print("Stack is Full")
    else:
        stack.append(item)
        print("Stack")


def pop(stack):
    if isEmpty(stack):
        print("Stack is Empty")
        return None
    else:
        return stack.pop()

---

분명히 제일 쉬운 자료구조인데, 문제에 적용하는게 너무 어렵다... 봐도 떠오르질 않고 그 개념을 이해하는데도 한참인데 참 쉽지 않다... 있는 문제라도 일단 열심히 풀면서 꾸준히 해나가자.

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다.

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지