Stack #1

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

이는 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 메서드가 알아서 내부 동작을 수행하기 때문에 편리하다.