data_structure
3. 스택
hoho0311
2024. 10. 7. 21:55
가장 단순 집어넣고 빼고
뺼 때는 맨 위부터 가능 (마지막에 들어간 것.)
스택이란
- 스택은 마지막에 추가된 요소가 가장 먼저 제거되도록 설계한 선형 데이터 구조
- 후입선출(LIFO : Last In First Out ) - 마지막에 삽입된 요소가 가장 먼저 제거
- 주요 연산으로는 push, pop, peek 등등이 있다
삽입과 삭제가 가장 핵심적인 연산이다.
스택오류 방지 : 스택의 크기를 적절히 관리, 삽입/ 제거를 수행하기 전 스택의 상태 확인
연산 모음
- inti() : 스택을 초기화한다.
- push(e) : 요소 e를 스택의 맨 위에 추가한다.
- pop() : 스택의 맨 위에 있는 요소를 꺼내 반환한다.
- is_empty() : 스택이 비었으면 TRUE를 아니면 FALSE를 반환한다.
- is_full() : 스택이 차있으면 TRUE를 아니면 FALSE를 반환한다.
- peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다. (확인 용도)
- 스택이 포화 상태이면 push()가 수행되어도 입력될 수 없으므로 오류가 발생한다. 이를 스택 오버플로우(overflow)라고 한다.
- 스택이 공백이면 pop()이나 peek()를 호출했을 때 삭제나 참조가 불가능하다. 이럴 때 스택 언더플로우(underflow)라고 한다.
스택의 활용 분야
- 되돌리기(undo), ‘이전 페이지 이동’
- 괄호 사용 검사, 계산기 프로그램
- 운영체제에서도 스택을 사용. 함수 호출과 반환을 위해 시스템 스택을 사용.
괄호 사용 검사
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef char Element; // 스택 요소 Element의 자료형
#include "ArrayStack.h" // 스택의 ADT(데이터와 연산) 포함
int check_matching(char expr[])
{
int i = 0, prev; // prev는 previous로 이전의 항목을 나타냄
init_stack();
while (expr[i] != '\\0') {
char ch = expr[i++];
if (ch == '[' || ch == '(' || ch =='{')
push(ch);
else if (ch ==']' || ch == ')' || ch == '}') {
if(is_empty())
return 2; // 조건 2 위반
prev = pop();
if ((ch==']' && prev != '[')
|| (ch == ')' && prev != '(')
|| (ch == '}' && prev != '{'))
return 3; // 조건 3 위반
}
}
if (!is_empty()) return 1; // 조건 1 위반
else return 0; // 괄호 정상
}
int main()
{
char expr[4][80] = {
"{A[(i+1)]=0;}",
"if((i==0( && (j==0)",
"while(n<8)){n++};",
"arr[(i+1]) = 0;,"
};
for (int i = 0; i<4 ; i++){
int errCode = check_matching(expr[i]);
if (errCode == 0) printf("%-20s -> 정상\\n", expr[i]);
else printf("%-20s -> 오류(조건%d 위반)\\n", expr[i], errCode);
}
return 0;
}
후위 표기식 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef double Element;
#include "ArrayStack.h"
double eval_postfix(char expr[])
{
int i = 0;
init_stack();
while (expr[i] != '\\0') { //expr = expression (표현식)
char c = expr[i++];
if (c >= '0' && c <= '9') {
double num = (double)c - '0';
push(num);
}
else if (c == '+' || c == '-' || c == '*' || c == '/') {
double val2 = pop();
double val1 = pop();
switch (c) {
case '+': push(val1 + val2); break;
case '-': push(val1 - val2); break;
case '*': push(val1 * val2); break;
case '/': push(val1 / val2); break;
}
}
}
return pop();
}
int main()
{
char expr[2][80] = { "8 2 / 3- 3 2 * +", "1 2 / 4 * 1 4 / *" };
printf("수식 : %s = %lf\\n", expr[0], eval_postfix(expr[0]));
printf("수식 : %s = %lf\\n", expr[1], eval_postfix(expr[1]));
return 0;
}