[Data Structure] 스택(Stack)

스택(Stack)

- 스택이란 물건을 쌓아 올린 것 처럼 자료를 쌓아 올린 형태의 자료구조 이다.

- 스택에 저장된 자료는 자료간의 관계가 1대1의 관계를 갖는 선형 구조이다. (반대의 경우는 1대N 구조인 트리가 있다.)

- 가장 마지막에 들어간 자료가, 가장 처음에 나온다. (후입선출 LIFO(Last-in-First-out))

- 위와 같은 특징 떄문에, 가장 위에서만 데이터의 삽입 & 삭제가 일어난다. 프링글스 통을 생각하면 된다.

스택의 데이터 구조

- top : 스택의 가장 위에 있는 위치를 저장하고 있는 데이터

- size : 스택의 크기를 저장하고 있는 데이터

- items : 스택에 담길 데이터를 저장할 데이터 구조

스택의 연산

- CreateStack : 스택을 생성하는 연산. size 필요
- IsEmpty : 스택이 현재 비어있는지 확인. True, False 리턴
- Push : 스택에 새로운 데이터 요소를 삽입하는 연산
- Pop : 스택에서 가장 위에 있는 요소를 반환하고 제거
- Peek : 스택에서 가장 위에 있는 요소를 반환

Python 에서 Stack 구현하기

Python에서 자료형 List를 사용하여 Stack을 구현할 수 있다.

class Stack:
    def __init__(self, size):
        # stack이 최초 생성 될 때 필요한 정보들
        self.size = size	# stack의 크기
        self.arr = [None for _ in range(size)]   # stack을 저장할 자료 구조
        self.top = -1	# stack의 최상단

    def __len__(self):
        # len() 함수 사용하였을 때 길이 반환
        return self.top + 1

    def is_empty(self):
        # 스택이 비어있는지 확인하는 함수.
        # top이 -1 이라면 True 반환
        if self.top == -1:
            return True
        else:
            return False

    def is_full(self):
        # 스택이 가득 차있는지 확인하는 함수.
        if self.top == self.size - 1:
            return True
        else:
            return False


    def push(self, n):
        # top 위치에 값을 입력
        if not self.is_full():
            self.top += 1
            self.arr[self.top] = n

    def pop(self):
        # 스택에서 top 위치에 있는 값을 반환하고 제거하는 함수
        if not self.is_empty():
            result = self.arr[self.top]
            self.arr[self.top] = None
            self.top -= 1
            return result
        else:
            return None

    def peek(self):
        # 스택에서 top 위치에 있는 값을 반환
        if not self.is_empty():
            return self.arr[self.top]
        else :
            return None