Stack 이란?

Stack은 데이터의 삽입과 삭제가 저장소의 맨 윗부분(top)에서만 일어나는 자료구조이다.
스택은 데이터가 순서대로 저장되고 스택의 마지막에 넣은 요소가 처음으로 꺼내지는 저장소의 구조를 가지고 있기때문에,
LIFO (Last In First Out) 이라고 불린다.
Stack은 연속으로 저장된 데이터 구조를 가지고 있고 맨 위 요소에 대한 주소값을 가지고 있는 어레이나 싱글 링크드 리스트로 구현이 가능하다.

Stack의 장점?

• 참조 지역성 (한번 참조된 곳은 다시 참죌 확률이 높다) 라는 특성을 활용할 수 있다.

Stack의 단점?

• 데이터를 탐색하기가 어렵다(중간에 데이터들이 들어가있으면 중간값을 뺄 수 없다.)

Stack의 구현시 메소드(추상 자료형)

1. push : 맨위에 값을 추가한다.
2. pop : 가장 최근에 넣은 맨위의 값을 출력하고 제거한다.
3. peek : 스택의 변형 없이 맨 위에 값을 출력
4. is_empty : 스택이 비어있는지 확인한다.

Stack 의 구현

• 파이썬의 배열은 동적배열이기 대문에 배열에 새로운 원소를 삽입, 삭제할 수 있다.
• List 변수에는 첫번재 원소의 주소값이 저장되기 대문에 맨 마지막으로 삽입한 원소의 인덱스도 바로 구할 수 있다.
• 이점 때문에 파이썬 에서는 List로도 Stack을 구현 할 수 있다. 이때 push, pop의 시간 복잡도는 O(1)이다.

간단한 스택구현

# 간단한 스택 구현
stack = [] # 스택을 리스트로 만든다
stack.append(1)		# 스택에 1을 넣는다.
stack.append(2)		# 스택에 2를 넣는다.
print(stack)		# 스택 출력
print(stack.pop())	# 스택에 맨윗 원소를 꺼낸다. == 2
print(stack.pop())  # 스택에 한번더 맨윗 원소를 꺼낸다. ==1

클래스를 활용한 스택구현

class Stack:
    def __init__(self)l
    	self.items = []
      
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        return self.items.pop
      
    def peek(self);
    	return self.stack[-1]
    
    def isEmpty(self):
        return not self.items
 
if __name__ == "__main__":
    stack = Stack()     
    print(stack)		
    print(stack.isEmpty())  # 처음엔 아무것도 들어있지 않으므로 True
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.peek())
    print(stack.pop())	
    print(stack.pop())
    print(stack.isEmpty())  # 모든원소를 내보냈으므로 True
      

Stack의 사용사례

1. 재귀 알고리즘
   • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
   • 재귀함수를 빠져나와 퇴각 검색을 할 때는 스택에 넣어 뒀던 임시 데이터를 빼줘야 한다.
   • 스택은 이런 행위를 직관적으로 가능하게 한다.
   • 스택은 재귀 알고리즘을 반복적 형태를 통해서 구현할 수 있게 해준다.
2. 웹브라우저 방문기록
   • 웹 웹브라우저의 히스토리는 차곡차곡 쌓여 뒤로가기 버튼을 누를때 스택에 pop을 해서 이전 페이지를 보여주는데 유용하다.
3. 실행취소
   • 웹브라우저의 뒤로가기 기능과 같다.
4. 역순 문자열 만들기
5. 수식의 괄호 검사(연산자 우선순위를 위해) => 후위 표기식 만드는데 사용된다.