스택 (Stack)

특징

• FILO(First in, Last out)형태의 자료구조를 가진다.
• push, pop(마지막 데이터 출력 및 제거)으로 데이터 입출력을 한다.
• Stack 맨 밑과 위에 있는 데이터를 bottom, top이라 말한다.

FAQ

• 리스트를 세워서 쓰면 스택이랑 같은게 아닌가?
  • 리스트에는 강력한 연산들이 있어서 스택은 push와 pop만 사용할 수 있기 때문에 제한적으로 사용하기 위해서 스택을 사용한다
  • 하지만 스택을 class로 선언할 때 리스트로 생성하기 때문에 간접적으로 리스트를 사용한다.

• len() 메소드를 쓰기 위해서는 __len__ 이라는 함수를 생성한 후 사용할 수 있다.
• len() 메소드 또한 상수 시간복잡도를 가진다.
  • items라는 리스트에서 원소 개수를 항상 관리하기 때문이다

Stack 활용 예시

1. 괄호

괄호를 입력 받았을 때 올바른 형식일 경우 True, 아닐 경우 False를 출력

input : (()())
output : False

input : ((())()(
output : False

Stack에 괄호를 넣고 ( 다음에 (가 올 경우 push, )의 경우 pop을 진행하며, 입력이 끝난 후 Stack의 길이가 0보다 클 경우 False 아닐 경우 True를 출력한다.

2. 계산기

infix 형태의 수식을 postfix 형태로 변환하기

input : +, -, *, /, (, ), 숫자(영문자)로 구성된 infix 수식
output : postfix 수식

ex)
2 + 3 * 5 (infix) = 2 3 5 * + (postfix)
2 * 3 + 1 = 2 3 1 * +

연산자를 Stack에 넣고 연산 우선순위에 따라 pop을 진행하며 출력한다.

1. 연산 우선순위에 따라 괄호를 친다.
2. 연산자의 오른쪽 괄호 다음으로 연산자를 이동한다.
3. 괄호를 지운다.

++ )가 입력 될 경우 (가 나올때 까지 연산자를 모두 pop

우선순위 ( < +, - < *, / < )

2-1. 계산기2

postfix형태의 수식을 계산하기

input : postfix 형태의 수식
output : 수식을 계산한 결과 값

피연산자를 Stack에 넣고 연산자를 입력받을 경우 2번의 pop을 해서 결과값을 push하여 Stack에 다시 넣고 최종 결과값을 출력한다.

출처 : 신찬수 한국외대 교수님