4.1 스택이란?
-스택: 뭔가를 쌓아놓은 더미, 후입선출
입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
- 스택 상단 : 입출력이 이루어지는 부분
- 스택 하단: 반대쪽 바닥부분
- 요소: 스택에 저장되는 것
- 공백 스택: 스택에 요소가 하나도 없을 때
*자료 출력순서가 입력순서 역순으로 이루어져야 할 경우 유용
*함수호출 이후 자신을 호출한 함수로 되돌아갈 때 호출된 역순으로 되돌아가야 하므로 스택 사용(복귀할 주소 기억에 사용)
-시스템 스택에는 함수가 호출될때마다 활성레코드가 만들어지며 여기에 복귀주소가 저장된다. (활성레코드에는 프로그램 카운터, 함수호출시 매개변수, 함수 안에서 선언된 지역 변수 같이 생성)
-함수호출 일어나면 항상 시스템 스택에 동일한 방법으로 저장 > 함수가 자기 자신 호출해도 동일한 방법으로 활성 레코드가 만들어졌다가 없어진다.
[추상 자료형 스택]
스택을 추상 자료형으로 정의 : 0개 이상의 요소를 가지는 선형리스트의 일종, 스택에 요소를 추가하거나 삭제하는 연산과 함께 현재 스택상태를 검사하는 연산들로 구성
-두가지 기본연산 : 1. 삽입(push) 2. 삭제(pop) -> push연산 중 스택 가득 차서 입력불가, pop연산중에 스택에 데이터 없어서 출력불가 >> 오류발생!!
+ is_empty, is_full 연산: 스택이 공백상태에 있는지, 포화상태에 있는지
+create 연산: 스택생성
+peek연산: 요소를 스택에서 삭제하지 않고 보기만 함
4.2 스택의 구현
1. 1차원배열 :
- int 형의 1차원배열 stack[MAX_STACK_SIZE] 필요. 스택에서 가장 최근에 입력됐던 자료 가리키는 top변수 필요, 가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장.
- top변수는 스택 비어있으면 -1의 값 가짐 (top 값이 0이면 배열의 인덱스 0에 데이터 있다는 것 의미)- push()에서 스택에 새로운 요소 삽입하기 전에 스택이 가득 차지 않았나 검사해야 함.(is_full 호출)> 차 있으면 오류메시지+함수반환, 먼저 top값을 증가해야 한다.(top을 증가시키지 않고 삽입하면 마지막 요소 지워짐)-pop(): 스택에서 하나의 요소 제거하는 연산, top이 가리키는 요소를 스택에서 꺼내어 외부로 건네준다. 요소 제거 전 스택 공백여부 확인 위해 is_empty() 호출하여 검사.
4.3 동적 배열 스택
-컴파일 시간에 크기 결정되는 1차원 배열> 컴파일 시간에 필요한 스택 크기 알아야 함> 어려움
C언어에서는 malloc() 호출하여 필요할떄마다 메모리 할당> 스택크기 동적으로 늘림
4.4 스택의 응용: 괄호 검사문제
조건:
1. 왼쪽 괄호 개수, 오른쪽 괄호 개수가 같아야 함.
2. 같은 종류 괄호에서 왼쪽괄호는 오른쪽 괄호보다 먼저 나와야함
3. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안됨.
알고리즘: 왼쪽 괄호 만나면 스택에 삽입, 오른쪽 괄호 만나면 스택에서 맨 위 괄호 꺼내고 오른쪽 괄호와 짝 맞는지 검사.
4.5 스택의 응용: 후위 표기 수식의 계산
*컴파일러는 주로 후위표기 사용
-중위표기식-> 후위표기식 과정 : 피연산자는 바로 후위표기수식에 출력, 가장 나중에 스캔된 연산자가 가장 먼저 출력
4.6 스택의 응용: 미로 문제
미로탈출 : 시행착오방법(한 경로 선택해서 시도하고 안되면 다른 경로 시도), 현재의 경로가 안 될 경우 다른 경로들이 어딘가에 저장돼 있어야 함.(현재위치에서 가능한 경로 중 가장 가까운 경로) >> 가장 최근 저장한 경로가 쉽게 추출되는 자료구조 사용해야 함.>> 스택!!
'자료구조' 카테고리의 다른 글
| [자료구조] chap6. 연결리스트 I (1) | 2024.10.18 |
|---|---|
| [자료구조] chap5. 큐 (0) | 2024.10.17 |
| [자료구조] chap3. 배열, 구조체, 포인터 (0) | 2024.10.12 |
| [자료구조] chap2. 순환 (0) | 2024.10.07 |
| [자료구조] chap1. 자료구조와 알고리즘 (2) | 2024.09.24 |