학습 노트/알고리즘 (Python)

Stack #1

걔랑계란 2022. 6. 4. 00:46

Stack 구조


Stack은 기본적으로 위와 같이 출구와 입구가 하나인 구덩이의 모습을 한다.
폰 스택(phone stack) 놀이와 같이 바닥에 깔려 있는 내 전화에서 벨이 울린다고
위에 있는 다른 전화를 건들지 않고 내 것만 쏙 빼서 확인할 수 없다.

Stack도 마찬가지이다.
가령 index 4에 접근하기 위해서는 7, 6, 5를 순서대로 접근한 후에야 4에 접근할 수 있다.
이러한 특징 때문에 Stack을 LIFO(Last In First Out/후입 선출) 구조라고 정의하기도 한다.

Pointer
Stack에 현재 저장돼 있는 데이터의 수를 나타낸다.
고정길이 스택의 경우
Pointer <= Capacity가 성립한다.

Capacity
Stack에 최대로 저장할 수 있는 데이터의 수이다.
고정길이 스택의 경우
Capacity = len(Stack)이 성립한다.

Bottom
Stack에서 가장 아래에 깔린 데이터를 Bottom이라고 한다.
Bottom은 자신보다 나중에 저장 된 데이터가 처리되기 전까지 처리될 수 없다.
Bottom = Stack[0]이 성립한다.

Top
Stack에서 가장 위에 존재하는 데이터를 Top이라고 한다.
통상 가장 마지막에 저장 된 데이터를 말하고, index는 0부터 시작하므로 고정길이 스택의 경우
Top = Stack[Capacity -1]
가변 길이 스택의 경우
Top = Stack[-1]이 성립한다.

Push
Stack에 새로운 데이터를 추가하는 동작을 의미한다.
새롭게 저장되는 데이터의 index는 항상 이전의 top 위에 위치한다.

Pop
Stack에 저장된 데이터를 추출하는 동작을 의미한다.
논리적으로는 맨 위의 데이터가 사라지지만 pointer를 하나 감소시키는 것으로
index 접근을 차단한다.

 

구현

Stack을 구현하는 방법은 여러 가지가 있지만,
Python의 list를 사용하면 쉽게 구현하거나 사용할 수 있다.

 

5. Data Structures — Python 3.10.4 documentation

5. Data Structures This chapter describes some things you’ve learned about already in more detail, and adds some new things as well. 5.1. More on Lists The list data type has some more methods. Here are all of the methods of list objects: list.append(x)

docs.python.org

이는 Python의 list가 이미 pop, append 등 Stack의 기능과 동일한 역할을 하는
메서드를 제공하기 때문이다.

class Stack1():
  def __init__(self):
    self.stk = []

  def push(self, val):
    self.stk.append(val)

  def pop(self):
    if self.is_empty():
      print('stk is empty')
    return (self.stk.pop())

  def top(self):
    if not self.stk:
      print('stk is empty')
      return
    return self.stk[-1]
  
  def bottom(self):
    if not self.stk:
      print('stk is empty')
      return
    return self.stk[0]

  def pointer(self):
    return len(self.stk)

Stack의 각각의 요소와 기능은 위와 같이 list가 제공하는 메서드와 속성으로 충분히 대체할 수 있다.
클래스 Stack1은 가변길이 스택을 정의하는 클래스로,
고정길이 스택에서 필요했던 Capacity는 필요 없다.
list에서 제공하는 append 메서드가 push를 대체하고, pop 메서드가 알아서 내부 동작을 수행하기 때문에 편리하다.

'학습 노트 > 알고리즘 (Python)' 카테고리의 다른 글

Stack #2  (0) 2022.06.23
Stack #1  (0) 2022.06.04
선형 데이터 구조와 탐색  (0) 2022.05.03
Q1. 방 배정 하기  (0) 2022.04.22
Python #3  (0) 2022.04.18
Python #2  (0) 2022.04.15