1. Stack - 파이썬 스택 공부하기

스택이란?

스택은 후입선출 (Last-In-First-Out) 방식의 자료구조이다.

파이썬은 스택 자료형을 직접적으로 제공하지는 않지만, 리스트가 그 기능을 지원한다.

 

스택의 메소드

• push() : 컬렉션에 요소를 추가한다. O(1)
• pop()  : 컬렉션의 가장 최근에 추가된 요소를 제거한다. O(1)

 

파이썬으로 스택 구현

여기서는 Linked-List를 이용한 Stack 추상자료형(ADT)를 구현한다.

Stack의 요소는 Node라는 Linked-List형태이다.
Stack에서 pop() 메소드를 사용하면, 가장 마지막에 추가된 Linked-List가 순서대로 제거된다.

# Linked-List를 Stack으로
class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class Stack:
    def __init__(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        if self.last != None:
            item = self.last.item
            self.last = self.last.next
            return item
        else:
            return None

if __name__ == '__main__':
    stack = Stack()
    stack.push(1) # 1->None
    stack.push(2) # 2->1->None
    stack.push(3) # 3->2->1->None

    for _ in range(3):
        print(stack.pop()) # 3, 2, 1