[Python] 스택(Stack) 구현

스택이란?

LIFO(후입선출) : 나중에 들어온 데이터가 먼저 나가는 구조
데이터의 삽입과 삭제가 한쪽에서만 수행되는 구조입니다.

1. 리스트를 이용한 Stack 구현

먼저 파이썬 클래스로 생성합니다.

class Stack(object):
    # 생성자
    def __init__(self):
        self.items = []        # 값을 담아줄 스택 형태의 배열

다음의 기능을 추가합니다.

• push : 스택의 맨 위에 항목 삽입
• pop : 스택의 맨 위 항목을 반환,삭제
• top/peek :스택 맨 끝의 항목을 조회
• empty : 스택이 비어있는지 확인
• size : 스택의 크기를 확인

    # 스택이 비었는지 확인하는 함수(Empty : True / Not Empty : false)
    def isEmpty(self):
        return not self.items

    # pop : 스택의 맨 끝의 요소 반환, 삭제
    def pop(self):
        # 스택이 비어있다면
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            value = self.items.pop()  # 리스트의 가장 마지막 요소 반환, 삭제 후 value에 저장
            return value

    # push : 스택의 맨 끝에 요소 삽입
    def push(self, value):
        self.items.append(value)

    # size : 스택의 크기 조회
    def size(self):
        return len(self.items)

    # peek / top : 스택의 맨 위의 항목 조회
    def peek(self):
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            return self.items[-1]    # 리스트의 마지막 값

     def __repr__(self):
        return repr(self.items)

결과 확인

if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었습니까 ? {}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    print("Stack : {}".format(stack))
    print("스택의 크기 : {}".format(stack.size()))
    print("peek : {}".format(stack.peek()))
    print("pop : {}".format(stack.pop()))
    print("peek : {}".format(stack.peek()))
    print("Stack : {}".format(stack))


# 출력 값
# 스택이 비었습니까 ? True
# 스택에 값을 추가합니다.
# Stack : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 스택의 크기 : 10
# peek : 9
# pop : 9
# peek : 8
# Stack : [0, 1, 2, 3, 4, 5, 6, 7, 8]

2. 노드(Node)를 이용한 Stack 구현

노드를 먼저 생성해줍니다.

# 노드의 기본 모양
class Node(object):
    def __init__(self, value = None, pointer = None): # value와 pointer 초기화
        self.value = value
        self.pointer = pointer

Stack 구현

class Stack(object):
    def __init__(self):
        self.top = None    # 초기에 스택은 비어있으므로 top, count 초기화
        self.count = 0

    def isEmpty(self):
        return not bool(self.top)   # 스택의 Top이 비어있으면 Empty

    def pop(self):
        # 스택이 비어있다면
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            node = self.top           # 임시 node에 스택의 Top부터 담는다
            self.top = node.pointer   # node의 다음 가리키는 곳을 Top으로 지정
            self.count -= 1           # count 감소

            return node.value         # node의 값 반환(기존의 top의 값)

    def push(self, item):
        self.top = Node(item, self.top)   # 새로운 값과 기존의 Top을 포인터로 Node형식(값, 포인터)
        self.count += 1                   # count 증가

    def size(self):
        return self.count

    def peek(self):
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            return self.top.value

    # 스택의 요소를 Top부터 차례대로 출력하는 메소드 구현
    def printStack(self):
        node = self.top
        while node:        # node가 False가 될때까지 반복 (node의 값이 None일 때)
            print(node.value, end=" ")
            node = node.pointer        # pointer를 다음 구간으로 계속 갱신
        print()

결과 확인

if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었습니까? {}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    stack.printStack()
    print("스택의 크기 : {}".format(stack.size()))
    print("peek : {}".format(stack.peek()))
    print("pop {}".format(stack.pop()))
    print("peek : {}".format(stack.peek()))
    stack.printStack()


# 출력값
# 스택이 비었습니까? True
# 스택에 값을 추가합니다.
# 9 8 7 6 5 4 3 2 1 0 
# 스택의 크기 : 10
# peek : 9
# pop 9
# peek : 8
# 8 7 6 5 4 3 2 1 0 

이상으로 두 가지 방법의 스택 구현에 대한 정리를 마치겠습니다.