Data Structure - Stack

1.. Stack 이란?

• "쌓다"라는 의미로, 데이터를 쌓아 올린 형태의 자료구조
• 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에 사용
• 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조
  Last In First Out(LIFO)
  

2.. Stack의 정의 및 성질

class Stack:
	def __init__(self):
    	self.items = []
        # 데이터 저장을 위한 리스트 준비
        
    def push(self, val):
    	self.items.append(val)
        # 데이터 삽입(원소 추가)
        # Time Complexity = O(1)
        
    def pop(self):
    	try:
        	return self.items.pop()
        except IndexError:
        	print("Stack is empty")
        # 데이터 삭제(원소 제거)
        # Time Complexity = O(1)
            
    def top(self):
    	try:
        	return self.items[-1]
        except IndexError:
        	print("Stack is empty")
        # Stack된 items 중 가장 나중의 데이터 출력(제일 상단의 원소 확인)
        # Time Complexity = O(1)
	
    def __len__(self):
    	return len(self.items)
        # Stack되어 있는 item의 수를 반환
        # Time Complexity = O(1)
        
*** 제일 상단이 아닌 나머지 원소들의 확인 및 변경은 원칙적으로는 불가능함 ***
*** 즉, Stack에서는 해당 기능을 제공하지 않음 ***