Python으로 구현하는 자료구조 : Stack

Python으로 Stack을 구현해보고

Stack 자료 구조의 특징과 데이터의 삽입과 삭제에 대해서 알아보도록 하겠습니다.

---

# Stack 이란

Stack은 데이터의 삽입과 삭제가 저장소의 맨 윗 부분(the top of stack)에서만 일어나는 자료구조입니다. 

스택은 데이터가 순서대로 저장되고 스택의 마지막에 넣은 요소가 처음으로 꺼내집니다(LIFO : Last-in, First-out").  Stack은 연속으로 저장된 데이터 구조를 가지고 있고 맨 위 요소에 대한 포인터(주소값)을 가지고 있는 Array나 singly linked list로 구현할 수 있습니다.

Stack의 장점은, (1) 참조 지역성(한번 참조된 곳은 다시 참조될 확률이 높다)을 활용할 수 있다는 점이며, 

Stack의 단점은, (1) 데이터를 탐색하기가 어렵다는 점입니다.

Stack은 함수의 콜스택, 문자열을 역순으로 출력하거나 연산자 후위표기법 등에 사용됩니다.

# Stack의 ADT (abstract data type) 

( ★  : 필수 구현 메소드 )

★ push ( → None ):  맨 위에 값 추가

★ pop ( → data ): 가장 최근에 넣은 맨 위의 값을 제거

peak ( → data or -1 ) : 스택의 변형 없이 맨 위에 값을 출력

is_empty ( → boolean ): 스택이 비어있는지 확인

# Stack 구현하기 - List

Python의 List는 동적 배열(Dynamic array)이기 때문에 배열에 새로운 원소를 삽입, 삭제할 수 있습니다. List 변수에는 첫번째 원소(맨 아래)의 주소값이 저장되기 때문에 맨 마지막으로 삽입한 원소(맨 위)의 주소값도 바로 구할 수 있습니다. 이 점을 활용해서 List로 Stack을 구현할 수 있습니다. List를 사용하여 원소를 삽입(push), 삭제(pop) 작업을 수행했을 때는 시간복잡도는 O(1)입니다.

# List를 활용한 Stack 구현
class Stack(list):
    def __init__(self):
        self.stack = []
 
    def push(self, data):
        self.stack.append(data)
 
    def pop(self):
        if self.is_empty():
            return -1
        return self.stack.pop()
 
    def peek(self):
        return self.stack[-1]
 
    def is_empty(self):
        if len(self.stack) == 0:
            return True
        return False
 
 
if __name__=="__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    print(s.peek()) # 3
    print(s.pop()) # 3
    print(s.pop()) # 2
    print(s.pop()) # 1
    print(s.pop()) # -1 (더 이상 존재하지 않음)
 

# Stack 구현하기 - Singly linked list

Linked list의 head는 Stack의 가장 윗 부분을 가리킵니다. 이해를 돕기 위해 push가 어떻게 구현되었는지 그림으로 살펴보겠습니다. 1, 2가 쌓여있고 새로운 데이터 3이 추가되는 과정입니다. (1)새로운 Node(3)이 기존 head를 가리키고, (2) head가 새로운 node(3)을 가리키면 됩니다. 

# Singly linked list를 활용한 Stack 구현
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class Stack:
    def __init__(self):
        self.head = None
 
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    def pop(self):
        if self.is_empty():
            return -1
        data = self.head.data
        self.head = self.head.next
        return data
 
    def is_empty(self):
        if self.head:
            return False
        return True
 
    def peek(self):
        if self.is_empty():
            return -1
        return self.head.data