stack

스택(stack)은 삽입과 삭제가 저장소의 맨 윗에서만 일어나는, 즉 제한적으로 접근할 수 있는 나열 구조이다.

• 접근 방법은 언제나 목록의 끝에서만 일어나 끝먼저내기 목록(Pushdown list)이라고도 한다.
• 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
• 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 한다.

about

스택의 장점은 참조 지역성이 높다는 것이다. 한번 참조된 곳은 다시 참조될 확률이 높다. 단점은 데이터를 탐색하기 어렵는 것이다.

함수의 콜스택, 문자열 역순 출력 등에 사용된다.

콜스택

콜스택은 함수의 호출을 기록하는 자료구조다. 만약 우리가 어떤 함수를 실행시킨다면, 우리는 스택 위에 무언가를 올리는(push) 행위를 하게 되고, 함수로부터 반환을 받을 때, 스택의 맨 위를 가져오게(pop)되는 것이다.

ADT(abstract data type)

*표시는 필수 구현 메소드다.

• *push: 맨 위에 값을 추가 return None
• *pop: 맨 위의 값을 제거 return data
• peak : 스택의 변형 없이 맨 마지막 값을 출력한다. return data or -1
• is_empty : 비어있는지 여부를 확인한다. boolean

python stack

자바의 util 에 기본적으로 스택을 제공해주기 때문에 따로 구현하지 않고 이 클래스를 사용하면 된다. 반면 파이썬은 스택 자료구조는 따로 제공하지 않아서, 기본 클래스인 list를 통해 스택을 흉내 낼 수 있다.

return not?

not is a boolean operator that returns the boolean inverse of the value. return returns the result of that operator. In other words, the expression should be read as return (not self.myReturnCode). Quoting the documentation:

class stack:
    def __init__(self):
        self.items=[]
    
    # pop 기능 구현
    def pop(self):
        stack_length=len(self.items)
        
        # 스택이 비어있을때는 에러메세지 출력
        if stack_length < 1:
            return "Stack is empty!"
            
        # 가장 위에 있는 item을 반환하며 삭제
        result = self.items[stack_length-1]
        del self.items[stack_length-1]
        return result
    
    # push 기능 구현
    def push(self,x):
        self.items.append(x)
        
    def peek(self):
    	return self.items[-1]
        
    # isEmpty 기능 구현
    def isEmpty(self):
        return not self.items

링크에서 직접 해볼 수 있다.