Stack

Stack (스택)

한 쪽 끝에서만 자료를 넣고 빼는 작업이 이루어지는 자료구조.

LIFO (Last In First Out / 후입선출) 방식으로 이루어져 나중에 넣은 데이터가 먼저 나온다.

가장 최근 스택에 삽입된 자료의 위치를 top이라 한다.

스택의 맨 위 요소 top에만 접근이 가능하기 때문에 top이 아닌 위치의 데이터에 대한 접근, 삽입, 삭제는 모두 불가능

 

push() : top에 새로운 데이터를 추가. 즉, 데이터를 스택에 넣는 연산

pop() : 가장 최근에 삽입된 맨 위의 데이터를 제거

peek() 또는 top() : 스택의 맨 위의 데이터를 꺼내지 않고 확인만

element: 항목, 요소. 스택에 저장되는 데이터

capacity: 스택의 초기 용량

empty: 공백상태. 스택에 항목이 하나도 없는 상태

full: 포화상태. 초기에 저장한 항목이 지정한 용량만큼 꽉 차서 더이상 항목을 넣을 수 없는 상태

top: 스택의 상단. 열려있는 곳. 데이터를 넣을 수 있는 위치

 

stack underflow : 스택이 비어있을 때 pop() 또는 peek() 연산을 시도할 시 발생. 꺼낼 게 없는데 꺼내려는 경우 발생

stack overflow : 스택이 꽉 찼을 때 push() 연산을 시도하면 발생. 더 이상 공간이 없는데 데이터를 넣으려는 경우 발생

 

스택은 top(맨 위)의 데이터만 직접 접근 가능

→ push, pop, peek 연산은 매우 빠름. 시간 복잡도는 보통 O(1)

스택은 중간이나 아래에 있는 요소에 직접 접근할 수 없음

• 임의 접근 불가능
• 원하는 데이터를 찾으려면 하나씩 꺼내보면서 탐색해야 함. → O(n) 시간이 걸림 (탐색에는 비효율적)

활용

• 재귀 알고리즘
• DFS 알고리즘
• 작업 실행 취소와 같은 역추적 작업
• 괄호 검사, 후위 연산법, 문자열 역순 출력 등

 

 

 

 

 

참고

 

https://yoongrammer.tistory.com/45

[자료구조] 스택 (Stack)

https://www.inflearn.com/courses/lecture?courseId=334939&tab=curriculum&type=LECTURE&unitId=245561&subtitleLanguage=ko

3. 스택 | 자료구조와 알고리즘 기초 (Data Structure and Algorithms)