Stack 이란?(개념, 동작, 구현)

스택이란? 선형적 자료구조이며 데이터를 삽입시 뒤에 누적며 데이터를 꺼낼때는 뒤에서부터 꺼내는 자료구조입니다.

나중에 들어온 데이터가 먼저 나간다고 하여 Last Input First Out 이라하여 LIFO 구조라고 합니다.

뒤에서만 접근이 가능하므로 제한적으로 접근한다고 볼수있으며, 선형적 자료구조입니다.

---

위와 같이 데이터를 넣으면 위로 쌓이고 꺼낼때는 위부터 나가게 됩니다.

---

C나 C++로 스택을 구현하기 위해서는 신경써야 할것이 많습니다.

그러나 파이썬은 list에 스택의 기능이 이미있어 파이썬에서는 구현하기가 쉽습니다.

C++로 구현하는 것은 나중에 올리도록 하겠습니다.

 

아래는 파이썬으로 간단하게 구현한 스택입니다.

class Stack:
    #자료를 저장할 리스트 생성
    def __init__(self):
        self.data = []
    
    #들어온 데이터를 리스트에 추가
    def push(self, data):
        self.data.append(data)
    #들어온 데이터를 뒤에서부터 삭제
    def pop(self):
        return self.data.pop()
    #현재 스택의 데이터 개수를 출력
    def length(self):
        return len(self.data)
    #현재 스택이 비어있는지 검사
    def empty(self):
        if len(self.data):
            return False
        else:
            return True

 

그렇다면 스택으로 할 수 있는것이 무엇이 있을까요?

보통 프로그램 작성시 사용하는 함수가 스택구조로 동작합니다.(Function call)

또한 재귀함수도 스택구조로 동작을 하게됩니다.

스택 자료구조를 이용한 DFS(Depth First Search)를 할수있습니다.

DFS는 알고리즘 파트에 따로 포스팅하도록 하겠습니다.