[자료구조/Data Structure] 파이썬으로 스택(Stack) 자료구조 알아보기

스택의 개념

한 쪽에서만 데이터의 삽입 및 삭제가 가능한 LIFO (Last In First Out) 또는 FILO (First In Last Out) 자료구조

 

스택의 동작구조

스택의 push

스택의 pop

이런식으로 push를 하게 되면 아래부터 데이터가 점진적으로 쌓인다고 생각하면 편하고 pop을 하게 되면 위에서 부터 데이터를 출력한다고 생각하면 된다.

일상생활에서 비슷한 예로 프링글스나 여러겹 쌓인 접시를 생각할 수 있다.

 

스택의 함수

• push(item) : item을 스택의 가장 윗 부분에 추가한다.
• pop() : 스택에서 가장 위에 있는 데이터를 제거한다.
• peek() : 데이터를 제거하지 않고 스택의 가장 윗 부분에 데이터를 리턴한다.
• isEmpty() : 스택이 비어있으면 True를 리턴한다. 그렇지 않으면 False를 리턴한다.

 

스택의 사용 예

• 문자열 역순으로 만들기
• 실행 취소 (Ctrl + Z)
• DFS (Depth-First-Search) 깊이 우선 탐색
• 후위 표기법 계산

 

파이썬을 활용한 스택 구현 (배열 활용)

class Stack():

    # 초기화
    def __init__(self):
        self.stack = []

    # 데이터 삽입
    def push(self, item):
        self.stack.append(item)

    # 맨 위 데이터 리턴 및 삭제
    def pop(self):
        if self.isEmpty():
            return 'empty..'
        return self.stack.pop()

    # 맨 위 데이터 리턴
    def peek(self):
        if self.isEmpty():
            return 'empty..'
        return self.stack[-1]

    # 스택이 비어있는지 확인
    def isEmpty(self):
        if len(self.stack) == 0:
            return True
        return False

 

파이썬을 활용한 스택 구현 (노드를 활용한 연결 리스트 스택)

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


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

    def push(self, data):
        node = Node(data)

        # 현재 head를 지금 들어오는 node의 next로 지정 다음 push일 때 옮기기 위함
        node.next = self.head
        self.head = node

    def pop(self):
        if self.isEmpty():
            return 'empty..'

        # 현재 head의 data를 return 그 후 head를 현재 head의 next로 할당
        data = self.head.data
        self.head = self.head.next
        return data

    def isEmpty(self):
        if self.head:
            return False
        return True

    def peek(self):
        if self.isEmpty():
            return False
        return self.head.data