👉 스택(Stack)

LIFO(Last-in-First-Out, 후입선출)

나중에 들어간 데이터가 가장 먼저 나오는 자료구조이다.

웹브라우저의 뒤로가기, DFS(깊이 우선 탐색), 후위 연산자의 연산(계산기) 등 에서 활용된다.
파이썬에서는 스택 자료형을 별도로 제공하지는 않지만 리스트가 스택의 모든 연산을 지원한다.

✍️ 리스트를 이용한 구현

class stack:
    def __init__(self):
        self.items = []
        
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        self.items.pop()
        
    def isEmpty(self):
        return not self.items

✍️ 연결리스트를 이용한 구현

class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next

class Stack_by_LinkedList:
	def __init__(self):
    	self.top = None
    
    def push(self, item):
    	self.top = Node(item, self.top)
    """
    Node 1개, self.top = {item:val1, next:self.top}
    Node 2개, self.top = {item:val2, next:{item:val1, next:self.top}}
    Node 3개, self.top = {item:val3, next:{item:val2, next:{item:val1, next:self.top}}}
     . . .
    """   
    
    def pop(self):
    	if self.top is None:
        	return None
            
        node = self.top
        self.top = self.top.next
        return node.item
    
    def is_empty(self):
        return self.top is None