1. 스택 Stack
스택 쌓는 말을 많이 들어보셨을 겁니다.
이 자료구조 또한 쌓아가는 형태를 가지는 자료구조를 말합니다.
1. 1. 가능한 작업
- push
- pop
- top
스택은 Push, Pop, Top 작업이 가능합니다.
가장 위에서 데이터를 삽입하고, 가장 위에서 데이터를 삭제하고 가장 위에 있는 데이터를 출력합니다.
이러한 특징으로 스택에서는 시간 순서에 따라서 데이터가 쌓입니다. = 후입선출, LIFO, Last In First Out
1. 2. 프로세스 4대 요소 중 하나
스택 자료구조는 프로세스 4대 요소 중 하나입니다.
| 프로세스 4대 요소 | |
| code | : 사용자가 작성한 프로그램 함수 |
| data | : 프로그램이 사용하는 데이터 공간으로 전역변수, Static 변수 |
| heap | : 프로그래머가 필요할 때 사용하는 공간 |
| stack | : 함수의 수행을 마치고 복귀할 주소 및 데이터로 지역변수, 매개변수, 리턴값 등 |
code가 가장 낮은 메모리 주소를 가지고 있고 stack이 높은 메모리 주소를 가지고 있습니다.
1. 3. 활용
- 웹 브라우저 방문기록 중 뒤로 가기 : 웹 브라우저 사용자가 새로운 페이지를 방문할 때마다 이전의 url을 스택 자료구조에 저장합니다. 뒤로가기 작업을 수행하고 싶으면, 스택에서 가장 최근 url을 꺼내서 이전 페이지로 이동 할 수 있습니다. 즉, 가장 마지막에 실행되었던 방문 기록을 보여주는 작업입니다.
- 실행 취소 (undo) : 가장 마지막에 실행 된 것을 실행 취소하는 작업
- 함수 호출 관리 : 재귀 함수처럼 함수 호출이 중첩되면, 각 함수 호출의 정보를 스택에 저장하고 함수가 종료되면 스택에서 하나씩 처리합니다. = 함수 호출 스택, 콜 스택, call stack
- 문자열 역순 변환 : 문자열을 역순으로 변환할 때 스택을 활용할 수 있습니다. 문자열을 하나씩 스택에 넣고, 스택에서 하나씩 꺼내면 문자열이 역순으로 바뀝니다.
- 괄호 검사 : 수식에서 괄호가 올바르게 짝을 이루는지 검사하는 데 스택을 활용할 수 있습니다. 수식에서 괄호가 짝을 이루는 경우는 ()[]{} 등 잘 닫힌 형태입니다. ((() 이 경우에는 짝을 이루지 않습니다. 여는 괄호를 스택에 넣고 닫는 괄호가 나올 때 여는 괄호를 꺼내서 짝이 맞는지 확인합니다.
- 중위 표기식을 후위 표기식으로 변환 : 중위 표기식은 1+2-3*4 이렇게 숫자 중간중간에 연산자가 들어간 형태의 식을 말합니다. 후위 표기식은 1 2 3 * - + 으로 표현됩니다.
- 트리 및 그래프 탐색 : 깊이 우선 탐색 DFS, depth-first search 알고리즘에서 스택 자료구조를 사용하여 다음에 방문할 노드를 추적할 수 있습니다.
2. 스택의 삽입 알고리즘 Push
자료구조 스택에서 데이터를 삽입하고 싶을 때는, 공간이 있다면 가장 위에 데이터를 삽입합니다.
if TOP>= n then call Stack-Full;
else TOP = TOP + 1;
Stack(TOP) = Data;
end Insert
n이 스택의 최대 크기를 의미합니다.
n이 Top보다 작거나 같다고 하면,
스택이 꽉 찬 상태라 삽입할 수 없습니다.
따라서 Stack이 Full일 때의 함수를 호출합니다.
n이 Top보다 크다면, 즉 최대 크기보다 Top이 낮게 위치한다면, Top을 한 자리 더 위로 높여주고,
그 Top 자리에 새로운 Data를 삽입하는 알고리즘입니다.
3. 스택의 삭제 알고리즘 Pop
자료구조 스택에서 삭제를 하고 싶을 때는, 스택이 비어있지 않으면, 가장 위에 있는 데이터를 삭제합니다.
if TOP = 0
then Underflow
Else
Remove Stack(TOP)
TOP = TOP - 1
TOP은 현재 가장 높이 위치한 인덱스라고 가정하고,
Underflow는 스택이 비어있을 때 호출되는 함수라고 가정하고,
Remove Stack(TOP) 은 스택의 가장 높은 곳에 있는 인덱스 위치에서 데이터를 삭제하는 함수라고 가정합니다.
만약 TOP의 값이 0이라면, 그 스택은 비어있는 것이므로 Underflow 함수를 호출합니다.
그렇지 않는다면, 즉 TOP의 값이 0이 아니라면, 그 스택은 비어있지 않으므로 데이터를 삭제할 수 있습니다.
TOP 위치에 있는 데이터를 삭제하고 TOP의 위치를 한 자리 더 아래로 낮춰줍니다.
4. 스택의 오버플로 알고리즘 Stack Buffer Overflow
TOP <- TOP + 1
if TOP > n
then goto AA
else
Stack(TOP) <- data
삽입과 마찬가지로 스택의 최대 크기보다 TOP이 크면, 스택의 오버플로우가 생긴 것이므로 다시 AA라는 위치로 돌아가도록합니다. * 스택 가드 Stack Guard
스택의 오버플로우가 생기지 않았다면 스택 TOP위치에 data를 추가합니다.
'자격증' 카테고리의 다른 글
| 큐 자료 구조 특징 | 큐의 수도 알고리즘 Pseudo Algorithm of Queue (0) | 2024.06.27 |
|---|
