본문으로 바로가기

Stack with Python

category DataStructure 2021. 3. 4. 00:44
728x90
반응형

Stack

스택은 배열에 몇 가지 제약사항을 추가한 자료구조이다. 제약사항이란 다음과 같다.

  • 스택의 끝에만 데이터를 삽입할 수 있다.
  • 스택의 끝에만 데이터를 삭제할 수 있다.
  • 스택의 마지막 원소만 읽을 수 있다.

즉 위 3가지 제약사항으로써 알 수 있는 건 Last In First Out이며 이 뜻은 먼저 들어간 놈이 맨 나중에 나오는 놈이다 라고 생각하면 됩니다.

Stack은 ADT이며 이는 추상 데이터 타입을 뜻한다. 이 뜻은 개발자나 프로그래머에 의해서 정의되어서 사용된다라는 의미이다. 적어도 Python에서 Stack이라는 자료구조가 built-in 되어 있지 않은 것으로 생각할 수 있다.

 

Definition

python에서 stack을 정의할 때는 일반적으로 다음과 같이 정의한다.

class Stack(object):
    def __init__(self):
        self.items = []

데이터를 담을 공간인 self.items가 python의 list로 정의되어있는 것을 볼 수 있다. 밑에부터는 stack에서 사용할 수 있는 method에 관한 것이다.

 

Push : stack의 데이터 삽입

stack에 데이터를 삽입하는 연산이다. python의 list 자료구조의 append를 사용하여 정의할 수 있다.

def push(self,value):
	self.items.append(value)

 

pop : stack의 데이터 삭제 

stack에 데이터를 삭제하는 연산이다. stack은 LIFO 구조이기 때문에 당연힌 맨 나중에 들어간 놈부터 차례대로 지워져야한다. python에서는 list의 pop을 사용하여 정의할 수 있다.

def pop(self):
    try:
        value = self.items.pop()
    except IndexError:
        raise Exception("Stack is Empty")

 

pop은 용례가 쫌 갈리는 것 같다. pop을 수행하는 과정에서 단순히 값을 지우기만 할 것인지 아니면 지운 값을 return을 해줄것인지에 대한 문제인데 어느 것이 맞는지는 찾지 못했다.

 

peek : stack의 맨 끝 항목을 조회

stack에 들어있는 맨 위의 항목을 조회하는 메서드이다. pop과 마찬가지로 python list를 다루는 것이다보니 IndexError가 일어날 수 있음에 주의하자.

def peek(self):
    if not self.items:
        raise Exception("Stack is Empty")

    return self.items[-1]

peek()의 경우 top()이라는 method를 정의해서 사용하는데 어떤 차이가 있는지는 잘 모르겠다.

 

is_empty : stack이 비어있는지 체크

stack의 데이터를 담는 내부 변수인 items는 python list이므로 list가 비었는지 차있는지 체크하면 된다.

def is_empty(self):
    return bool(self.items)

 

Stack Source 

class Stack(object):
    def __init__(self):
        self.items = []

    def push(self, value):
        self.items.append(value)

    def pop(self):
        try:
            self.items.pop()
        except IndexError:
            raise Exception("Stack is Empty")        

    def peek(self):
        if not self.items:
            raise Exception("Stack is Empty")

        return self.items[-1]

    def is_empty(self):
        return bool(self.items)

 

 

728x90
반응형