[자료구조] 스택을 알아보고 연결 리스트로 스택 ADT 구현하기

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 

---

스택(Strack)

 스택은 LIFO(Last In First Out, 후입선출)로 처리됩니다. 잔뜩 쌓아둔 접시를 떠올려보겠습니다. 마지막에 쌓은 접시가 맨 위에 놓일 것입니다. 그리고 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 됩니다. 스택도 마찬가지로 가장 마지막에 쌓은 데이터를 제일 먼저 꺼냅니다.

 

 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원합니다.

 

 스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형입니다.

• push(): 요소를 컬렉션에 추가합니다.
• pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거합니다.

---

연결 리스트를 이용한 스택 ADT 구현

 연결 리스트를 이용해 스택을 구현해보겠습니다.

 

 먼저 다음과 같이 연결 리스트를 담을 Node 클래스부터 정의합니다.

 

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

 

 이제 스택의 연산인 push()와 pop()을 담은 Stack 클래스를 다음과 같이 정의합니다.

 

class Stack:
    def __init__(self):
        self.last = None
        
    def push(self, item):
        self.last = Node(item, self.last)
        
    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item