스택(Stack)

Goal

• 스택을 구현할 수 있다. (배열 또는 연결리스트로 구현)
• 스택 구조를 그리고 스택에 대해 설명할 수 있다
• 스택이 사용되는 예시를 들 수 있고, 어떨 때 사용되는지 설명할 수 있다

---

스택(Stack)

• 한쪽 끝에서만 데이터가 삽입, 삭제가 일어나는 제한적 선형 자료구조
• 먼저 들어온 데이터가 나중에 출력되는 선입후출 FILO(First In Last Out) 형태의 자료구조 (FIFO = LIFO)

스택

 

성질

• 데이터의 삽입, 삭제가 한쪽 끝에서만 이루어지는 제한적 선형자료구조
• 선입 후출 FILO(First In Last Out) (= 후입 선출 : LIFO) 형태의 자료구조

(스택, 큐, 데크와 같이 삽입 삭제가 특정 위치에서만 제한적으로 이루어지는 자료구조를 제한적 선형자료구조라 한다)

 

특징

• 원소의 추가 O(1)
• 원소의 삭제 O(1)
• 최상단 원소의 확인 O(1) => 최상단이 아닌 위치의 원소는 확인 및 변경이 원치적으로는 불가능

스택의 추상 자료형 (ADT)

객체 : FILO(선입 후출)의 접근 방법을 유지하는데 필요한 요소들의 모음

연산

• push(x) : x를 스택의 최상단(top)에 추가
• pop() : 스택의 최상단 요소를 삭제
• isEmpty() : 스택이 비어있는지 결과 반환
• top() : 스택의 최상단 요소를 삭제하지 않고 반환 - peek()이라고 표현하는 곳도 있음
• size() : 스택의 요소 개수 반환
• isFull() : 스택이 꽉 찼는지 확인 (배열과 같이 제한된 크기를 가질 때 사용)

스택의 구현

BOJ 스택 구현 문제 : https://www.acmicpc.net/problem/10828

- 배열로 구현한 스택 - https://github.com/jihyuk124/DataStructure/tree/master/02.Stack/ArrayStack

- 링크드 리스트로 구현한 스택 - https://github.com/jihyuk124/DataStructure/tree/master/02.Stack/LinkedListStack

스택 구현 예시

• 괄호 검사 프로그램
• 수식 후위 표기법으로 계산하는 프로그램

참고)

컴파일러는 다음과 같은 이유를 중위 표기법 대신 후위 표기법을 사용한다

• 괄호 계산 없이 계산 순서를 알 수 있다
• 연산자 우선 순위의 고려가 필요 없다 (식 자체에 우선순위 포함)
• 수식을 읽으면서 바로 바로 계산이 가능

스택 사용 예시

스택은 선입후출형태의 자료구조이기 때문에 다음과 같은 상황에서 사용될 수 있다

• 함수의 Call Stack (함수 호출 순서 제어)
• 재귀적 문제 해결
• 후위 표기법
• 문서의 되돌리기 기능
• 괄호 검사
• (문자열 등의)역순 출력
• DPS(Depth First Search)를 사용해서 문제를 해결하는 경우