사자 위에 코끼리 위에 알파카가 올라타 있네요.

맨 밑에 있는 사자를 바로 꺼내려고 했다간 인형들이 와르르 무너져 내릴 겁니다. 그럼 우리 귀여운 인형들이 아파해요...

그니까 위에 있는 알파카랑 코끼리를 먼저 꺼내야겠죠? 이게 바로 스택입니다.

스택

• 후입선출 (LIFO, Last In First Out) 자료구조
  • 가장 나중에 넣은 데이터를 먼저 꺼냄
• 푸시: 스택에 데이터를 넣는 작업
• 팝: 스택에서 맨 마지막으로 입력한 데이터를 꺼내는 작업
  • 즉, 스택에서는 가장 나중에 푸시한 데이터가 먼저 팝됨

리스트를 이용한 스택 구현

• 파이썬에선 리스트로 스택을 구현할 수 있음
• .append()로 푸시를, .pop()으로 팝을 구현할 수 있음
  • .pop()은 팝한 원소를 반환

stack = []

# 스택에 데이터 푸시: .append()
stack.append(33)
stack.append(9)
stack.append(41)

# 스택에서 데이터 팝: .pop()
# 빈 스택에서 팝할 시, IndexError 발생하니 유의할 것
print(stack.pop())  # 41

# 다시 데이터 푸시
stack.append(1)
stack.append(10)

# 스택의 마지막 값 확인
print(stack[-1])    # 10

# 스택의 크기 구하기
stack_size = len(stack) # 현재 스택은 [33, 9, 1, 10]
print(stack_size)   # 4

# 다시 데이터 팝
print(stack.pop())  # 10

시간 복잡도

• .append(), .pop() 모두 리스트의 맨 끝에서 원소의 추가 / 삭제가 이루어짐
  • 기존 다른 원소들이 이동하지 않으므로, $O(1)$
• len: 길이 정보는 리스트 객체에 저장되어 있음, $O(1)$
• stack[-1]: 리스트 인덱싱이므로 $O(1)$

클래스를 이용한 스택 구현

• 코테 풀땐 이 정도까지 안 해도 되긴 하는데...
• 나중에 C언어 주차 때 어차피 이렇게 구현 시킬것 같아서 미리 알아두면 좋을 듯. C에는 .append() .pop() 그런 거 없으니~~
• Stack 클래스를 만듦
  • 크기, 즉 저장 가능한 최대 원소 수가 정해진 스택
  • 일단은 위의 푸시, 팝, 저장 원소 수 확인, 마지막 데이터 확인에 해당하는 기능만 구현해 보겠습니다

class Stack:
    def __init__(self, capacity=256):
        self.stk = [None] * capacity    # 값을 저장할 배열
        # 스택의 크기 (최대로 저장 가능한 원소 수)
        self.capacity = capacity
        # 스택 포인터 (현재 원소 수이자, 다음 원소를 저장할 인덱스)
        self.ptr = 0

    def push(self, value):
        # 스택에 value를 푸시
        if self.ptr >= self.capacity: # 스택이 찬 경우
            return         # 아무것도 하지 않음
        self.stk[self.ptr] = value
        self.ptr += 1

    def pop(self):
        # 스택에서 마지막 데이터를 팝
        if self.ptr <= 0: # 스택이 빈 경우
            return          # 아무것도 하지 않음
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self):
        # 맨 마지막 데이터를 확인
        if self.ptr <= 0: # 스택이 빈 경우
            return          # 아무것도 하지 않음
        return self.stk[self.ptr - 1]

    def __len__(self):
        # 스택의 데이터 수를 반환
        # 함수 len(obj)로 본 메서드 호출 가능
        return self.ptr

속성 정의

• self.capacity개의 원소를 저장할 수 있는 배열 self.stk 생성
• self.ptr의 최초 값은 0으로, 현재 저장된 원소 수이자 다음에 푸시할 때 원소가 저장될 위치를 나타냄
  • self.ptr이 0 이하면 리스트가 비어 있음
  • self.ptr이 self.capcity 이상이면 리스트가 꽉 차 있음

메서드 정의

• 푸시할 땐 self.ptr 인덱스 위치에 값을 저장 후, self.ptr을 1 증가
• 팝할 땐 self.ptr을 1 감소한 뒤, self.ptr 인덱스 위치의 값을 반환
• 마지막 데이터를 확인할 땐 self.ptr - 1번째 인덱스를 확인
• 길이를 확인할 땐 self.ptr을 반환
  • obj.__len__() 메서드를 정의하면, 이후에는 len(obj)로 호출 가능 (메서드 오버라이딩)

실제 동작과정

s = Stack(64)       # 최대 크기 64
s.push(33)
s.push(9)
s.push(41)
print(s.pop())      # 41
s.push(1)
s.push(10)
print(len(s))       # 4
print(s.peek())     # 10
print(s.pop())      # 10

문제풀이

2493. 탑

풀이가 길어져 별도 글로 대체