[알고 스터디] 1. 스택(Stack)

1. 스택(stack)

[Theory]

1.1 스택은 '선형 자료구조' !!

선형 자료구조 (linear structures)는 여러 개의 값을 선형적으로 가질 수 있는 구조이다.

선형 자료구조는 앞/뒤 로 끝을 가지며 각 끝마다 항목을 조절할 수 있다.

항목의 추가/삭제 방식에 따라 선형 자료구조의 종류가 나뉘게 된다.

스택 / stack
큐 / queue
덱 / deque
연결 리스트 / linked list
정렬 리스트 / sorted list

1.2 그래서 스택이 뭔데?

스택은 여러 개의 값을 가지며 값들 사이의 순서가 중요한 선형 자료형이다. 항목의 추가 및 삭제가 'top'이라 불리는 한쪽에서만 이루어진다. 다른 쪽은 'base'라고 부른다.

따라서 후입선출, Last-In-First-Out (LIFO) 로 작동한다.

우리가 매일 사용하는 인터넷 브라우저의 창 이동 방식이 바로 이 스택이다!

 

1.3 Stack 추상 자료형

- Stack() : 빈 스택 생성

- push(item)

- pop()

- peek()

- is_empty()

- size()

 

사용 예시를 보자면 이런 느낌이다.

스택 / 연산스택 / 항목반환값

s = Stack()	[]
s.is_empty()	[]	True
s.push(4)	[4]
s.push('dog')	[4, 'dog']
s.peek()	[4, 'dog']	'dog'
s.push(True)	[4, 'dog', True]
s.size()	[4, 'dog', True]	3
s.is_empty()	[4, 'dog', True]	False
s.push(8.4)	[4, 'dog', True, 8.4]
s.pop()	[4, 'dog', True]	8.4
s.pop()	[4, 'dog']	True
s.size()	[4, 'dog']	2

 

1.4 자, 그럼 사용법도 알았으니 직접 스택 클래스를 구현해볼까?!

class Stack:
    """리스트를 활용한 스택 구현"""

    def __init__(self):
        """새로운 스택 생성"""
        self._items = []

    def __repr__(self):
        """스택 표기법: <[1, 2, 3]> 등등"""
        return f"<{self._items}>"
        
    def is_empty(self):
        """비었는지 여부 확인"""
        return not bool(self._items)

    def push(self, item):
        """새 항목 추가"""
        self._items.append(item)

    def pop(self):
        """항목 제거"""
        return self._items.pop()

    def peek(self):
        """탑 항목 반환"""
        return self._items[-1]

    def size(self):
        """항목 개수 반환"""
        return len(self._items)

생성한 함수를 보면 알 수 있겠지만, 일단 스택을 구현하면 메인은 스택 생성자/항목추가/항목제거/빈스택확인/가장 위 항목 반환 등이 일반적이다.

 

근데 위는 <아래가 가장 첫 번째 요소인 경우>이다. 이때는 추가/제거 시, pop()/insert(item)인데,

만약, <스택의 탑을 첫 번째 요소로 정한 경우>에는 pop(0)/insert(0, item)으로 코드를 구성해야해서

시간복잡도가 O(1)에서 O(n)으로 증가하게 된다.

 

[Application]

<문제>

https://www.acmicpc.net/problem/2257

2257번: 화학식량