python, Stack

파이썬(python)으로 스택(stack) 자료구조를 구현해보자
파이썬에 내장되어 있는 Data-type중 리스트(list)를 이용하여 구현했다.

Stack 생성

Stack 클래스를 생성하고 init method를 이용하여 멤버 변수를 만들어준다.

class Stack:
    #리스트를 이용하여 스택 생성
    def __init__ (self):
        self.top = []

top 변수 안에는 파이썬에 내장되어 있는 리스트(list)를 이용하여 스택을 만들어 준다.

#스택의 크기를 출력
    def __len__(self):
        return len(self.top)

    #스택 내부 자료를 string으로 변환하여 반환
    def __str__(self):
        return str(self.top[::1])

__len__과 __str__를 작성한다.
len은 스택의 크기(길이)를 반환하고
str은 스택 내부에 저장된 모든 데이터를 string형태로 변환하여 반환하도록 한다.

구현 함수

push

#PUSH
    def push (self, item):
        self.top.append(item)

파이썬 list에 내장되어 있는 append함수를 사용하여 리스트 끝에 값을 추가한다.

pop

#POP
    def pop(self):
        #if Stack is not empty
        if not self.isEmpty():
            #pop and return 
            return self.top.pop(-1)
        else:
            print("Stack underflow")
            exit()

먼저 isEmpty를 호출하여 스택이 비어있는지 확인한다.
isEmpty는 직접 작성해주어야한다.

파이썬 list 안에 내장되어 있는 함수 pop에 -1이라는 인자를 넘겨
리스트 가장 마지막에 있는 데이터를 꺼낸다.

clear

#스택 초기화
    def clear(self):
        self.top=[]

Stack클래에 멤버변수인 top을 새로운 리스트로 초기화해준다.
기존 top에 있던 모든 데이터는 더이상 포인팅할 수 없다.

isContain

#자료가 포함되어 있는지 여부 반환
    def isContain(self, item):
        return item in self.top

peek

#스택에서 top의 값을 읽어온다
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            print("underflow")
            exit()

리스트 인덱싱을 이용하여 top리스트의 가장 마지막 원소(자료)를 반환시킨다.

isEmpty

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

size

 #스택 크기 반환
    def size(self):
        return len(self.top)

github

전체 코드는 github에 올려두었다.