[자료구조] 스택(Stack)

스택~~https://jamanbbo.tistory.com/54

[Stack]사칙연산 계산기 구현(2) - 후위 표기 수식 계산

 

1. 스택의 정의

삽입과 삭제가 한쪽 끝(top)에서만 이루어지는 자료구조

 

2. 스택의 특징

• 후입 선출로 가장 나중에 들어온 것이 가장 먼저 나간다

 

3. 스택의 연산

1) push

스택에 데이터를 추가

2) pop

스택에서 데이터를 삭제

3) isEmpty

스택이 공백상태인지 검사

4) isFull

스택이 포화상태인지 검사

5) peek

• 스택 top보기만 하는 연산
• 비어 있는 스택에서 실행하면 예외를 발생시킴

 

4. 스택의 구현

1) 배열로 구현

• top은 스택의 가장 위의 항목이 저장된 배열 원소의 인덱스
• 스택이 empty이면 top은 -1
• 장점
  • 구현이 쉽다
  • 데이터 접근 속도가 빨라 조회가 빠르다
• 단점
  • 크기가 정해져 있어야 한다

2) 연결리스트로 구현

• top은 스택의 가장 위에 있는 항목을 참조하는 레퍼런스
• 스택이 empty이면 top의 레퍼런스가 null
• 장점
  • 크기 제한이 없다
  • 삽입 삭제가 쉽다(상수 시간에 가능)
• 단점
  • 구현이 복잡하다
  • 배열보다 조회가 어렵다(상수시간에 조회가 불가능)
• 자바에서는 연결리스트로 Collection의 Stack을 제공한다

 

5. 스택의 특징

1) 복수 스택

• 하나의 배열을 이용하여 여러 개의 스택을 동시에 표현하는 방법
• 두 개의 스택인 경우 스택 0은 인덱스 맨 끝에서부터 확장, 스택 1은 인덱스 1부터 확장

 

6. 스택의 활용

컴파일러의 괄호 짝 맞추기, 회문 검사하기, 후위표기법 수식 계산하기, 중위표기법 수식의 후위표기법 변환, 리스트의 순서를 역순으로 만들기, 되돌리기 기능, 함수호출에서 복귀주소 기억, 시스템 스택, 실행 시간 스택 등

1) 중위표기법 수식의 후위표기법 변환

2) 후위표기법의 계산

3) 재귀 알고리즘

재귀적으로 함수를 호출해야 하는 경우 재귀함수 호출을 시작할 때 임시데이터를 스택에 넣는다

재귀함수에서 빠져나올 때 스택에 넣었던 임시데이터를 뺀다

 

7. 관련 문제

백준 1874

GitHub - Lee-Min-Jung/coding_test_practice

 

백준 17298

GitHub - Lee-Min-Jung/coding_test_practice