[자료구조/알고리즘] 스택(Stack)

스택(Stack)

• LIFO(후입선출)구조
• 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조입니다.
  데이터의 삽입과 삭제가 한쪽에서만 수행되는 구조입니다.

리스트를 이용한 Stack

• push : 스택의 맨 위에 항목 삽입
• pop : 스택의 맨 위 항목을 반환,삭제
• top/peek :스택 맨 끝의 항목을 조회
• empty : 스택이 비어있는지 확인
• size : 스택의 크기를 확인

class Stack(object):
    # 생성자
    def __init__(self):
        self.items = []   # 값을 담아줄 스택 형태의 리스트
    
    # 스택이 비었는지 확인하는 함수(Empty : True / Not Empty : false)
    def isEmpty(self):
        return not self.items
    
    # pop : 스택의 맨 끝의 요소 반환, 삭제
    def pop(self):
        # 스택이 비어있다면
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            value = self.items.pop()  # 리스트의 가장 마지막 요소 반환, 삭제 후 value에 저장
            return value
        
    # push : 스택의 맨 끝에 요소 삽입
    def push(self, value):
        self.items.append(value)
        
    # size : 스택의 크기 조회
    def size(self):
        return len(self.items)
    
    # peek / top : 스택의 맨 위의 항목 조회
    def peek(self):
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            return self.items[-1]    # 리스트의 마지막 값
        
    def __repr__(self):
        return repr(self.items)

if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었습니까 ? {}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    print("Stack : {}".format(stack))
    print("스택의 크기 : {}".format(stack.size()))
    print("peek : {}".format(stack.peek()))
    print("pop : {}".format(stack.pop()))
    print("peek : {}".format(stack.peek()))
    print("Stack : {}".format(stack))

스택이 비었습니까 ? True
스택에 값을 추가합니다.
Stack : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
스택의 크기 : 10
peek : 9
pop : 9
peek : 8
Stack : [0, 1, 2, 3, 4, 5, 6, 7, 8]

• 객체에 대한 정보를 프린트 구문으로 출력하게 만들어주는 메소드
  (당연히 print구문으로 객체들을 호출하면 객체의 주소값이 출력됨 -> repr, str 메소드 활용)

+ __repr__ : 객체의 official(공식적인) 정보를 출력     
 -> 시스템이 인식하는 대로, 객체의 모습 그대로를 호출하는 "딱딱한" 호출
+ __str__ : 객체의 informal(비공식적인) 정보를 출력     
 -> 사용자 입장에서 보기 쉬운, 조금은 "느슨한" 호출

노드를 이용한 Stack 구현

• 노드의 기본 모양을 먼저 정의합니다.

# 노드의 기본 모양
class Node(object):
    def __init__(self, value = None, pointer = None): # value와 pointer 초기화
        self.value = value
        self.pointer = pointer

• 정의된 노드를 활용하여 스택을 구현합니다.

# 스택 구현 
class Stack(object):
    def __init__(self):
        self.top = None    # 초기에 스택은 비어있으므로 top, count 초기화
        self.count = 0
        
    def isEmpty(self):
        return not bool(self.top)   # 스택의 Top이 비어있으면 Empty
    
    def pop(self):
        # 스택이 비어있다면
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            node = self.top           # 임시 node에 스택의 Top부터 담는다
            self.top = self.top.pointer   # node의 다음 가리키는 곳을 Top으로 지정
            self.count -= 1           # count 감소
            
            return node.value         # node의 값 반환(기존의 top의 값)
            
    def push(self, item):
        self.top = Node(item, self.top)   # 새로운 값과 기존의 Top을 포인터로 Node형식(값, 포인터)
        self.count += 1                   # count 증가
    
    def size(self):
        return self.count
    
    def peek(self):
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            return self.top.value
        
    def printStack(self):
        node = self.top
        while node:
            print(node.value, end=" ")
            node = node.pointer
        print()

if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었습니까? {}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    stack.printStack()
    print("스택의 크기 : {}".format(stack.size()))
    print("peek : {}".format(stack.peek()))
    print("pop {}".format(stack.pop()))
    print("peek : {}".format(stack.peek()))
    stack.printStack()

스택이 비었습니까? True
스택에 값을 추가합니다.
9 8 7 6 5 4 3 2 1 0 
스택의 크기 : 10
peek : 9
pop 9
peek : 8
8 7 6 5 4 3 2 1 0