[Algorithm] 스택

* Python을 기준으로 합니다

---

스택 (Stack)

- 개념

• 스택 : LIFO (Last In First Out) 형태의 자료구조
  • 처음 실행했던 위치로 돌아가기 위해 이전 실행들을 쌓아서 관리하는 용도
  • 삽입과 삭제를 핵심 연산으로 가짐
• 스택의 주요 연산
  • `push()` : 새로운 데이터를 스택의 맨 위에 추가
    
  • `pop()` : 스택의 맨 위에 위치한 데이터를 꺼내서 반환
    
  • `isEmpty()` : 스택이 비어있으면 `True`, 아니면 `False`
    
  • `peek()` : 스택 맨 위에 위치한 데이터를 확인
• Python에서의 스택 활용
  1. 일반적으로 리스트를 스택처럼 활용함
     • Python 리스트의 `append(), pop()`은 각각 `push(), pop()`에 대응
     • `isEmpty()`의 경우 리스트의 length를 활용 `len(stack) == 0`
     • `peek()`는 리스트의 slicing으로 접근할 수 있음 `stack[-1]`
  2. `queue` library를 import 하는 방법
     • 해당 library를 import 하면 `import queue`
     • 스택은 `LifoQueue()`로써 제공됨 `stack = queue.LifoQueue()`
     • 삽입 : `put()`, 삭제 : `get()`, 스택 상태 : `empty()`

- 구현

1. 배열을 통한 구현

• Python의 배열 구조에 해당하는 리스트를 활용함

stack = []

#stack 상태 확인
print(len(stack)==0) #True

#데이터 삽입
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)# [1,2,3]
print(len(stack)==0) #False

#데이터 삭제
stack.pop()
print(stack) #[1,2]
stack.pop()
print(stack) #[1]

2. 연결 리스트를 통한 구현

• 연결 리스트를 활용하여 구현할 수도 있음

class Node: #linked list node
    def __init__(self, data):
        self.data = data
        self.link = None

class Stack: #stack 
    def __init__(self):
        self.top = None

    def push(self, data):
        prev = self.top
        self.top = Node(data)
        self.top.link = prev

    def pop(self):
        pop = self.top.data
        self.top = self.top.link
        return pop

    def peak(self):
        return self.top.data
    
    def isEmpty(self):
        if self.top == None:
          return True
        else:
          return False

• 결과 확인

s = Stack()

print(s.isEmpty()) #True

#push
s.push(1)
s.push(2)
s.push(3)

print(s.peak()) #3
print(s.isEmpty()) #False

#pop
for _ in range(3):
  print(s.pop(), end=' -> ') #3 -> 2 -> 1 -> None
print('None')