[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

 

[ Contents ]

 

 

1. 스택(Stack)

스택(Stack): 후입선출(Last-in-First-out). 가장 최근에 들어간 자료부터 꺼내는 자료구조

 스택은 말 그대로 쌓는(stack) 자료 구조입니다. 아래서부터 차곡차곡 쌓은 다음, 위에서 하나씩 뺍니다. 밑에 있는 걸 억지로 뺄려고 하면 무너지겠죠..

 가장 마지막에 들어간 자료부터 꺼내며, 억지로 앞에 있는 자료를 꺼낼 수 없습니다.

 

 

 

2. 스택 함수

.push(a)	a 추가
.pop()	가장 최근 자료를 삭제하고 반환
.peek()	가장 최근 자료를 반환 (삭제 X)
.empty()	스택이 비어있으면 1, 아니면 0 반환

 스택 함수는 가장 마지막에 넣은 자료만 조작할 수 있습니다.

 

 

 

3. 스택 구현

class Stack:
    # top은 가장 최근 자료를 가리키는 포인터
    def __init__(self):
        self.top = []

    # 스택 크기 반환
    def __len__(self) -> bool:
        return len(self.top)

    # 스택 원소 삽입
    def push(self, item):
        self.top.append(item)

    # 스택 원소 삭제 및 반환   
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
        else:
            return -1 #반환값 없음(비어있음)

    # 스택 원소 반환
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            return -1 #반환값 없음(비어있음)

    # 빈 스택 여부
    def isEmpty(self) -> bool:
        return len(self.top) == 0

 일일이 스택을 구현하면 위와 같습니다. 구현 난이도가 어렵진 않지만, 매번 스택을 구현해서 사용하려면 힘듭니다.

 

 

from collections import deque

stack = deque() #생성

 파이썬에서는 collections의 deque 라이브러리를 사용합니다. deque는 스택과 큐의 기능을 모두 가진 객체입니다.

 

push(a)	stack.append()	a 추가
pop()	stack.pop()	가장 최근 자료를 삭제하고 반환
peek()	stack[-1]	가장 최근 자료를 반환 (삭제 X)
empty()	not stack	스택이 비어있으면 1, 아니면 0 반환

 deque에 peek과 empty 기능은 없습니다. 그 대신에 stack[-1]과 not stack으로 바꿔 사용할 수 있습니다.

 

 위 예시와 같이 사용합니다. stack[-1]은 맨 마지막 원소를 반환하며, stack은 자료 리스트를 반환합니다. 자료의 개수가 0(False)일 때가 비어있다는 의미이므로, not을 붙여서 empty 기능을 사용할 수 있습니다.