All
스택의 개념
•
후입선출(LIFO) : 가장 먼저 입력된 자료가 가장 나중에 출력
•
push와 pop 연산이 한곳(top)에서만 발생
•
0개 이상의 원소를 갖는 유한 순서 리스트
•
시간 복잡도 push pop O(1)
스택의 응용
•
변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
•
서브루틴 호출 관리를 위한 스택
•
연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
•
인터럽트의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택
•
컴파일러, 순환 호출 관리 등 활용
스택의 추상자료형
•
Stack: 0개 이상의 원소를 가지는 집합(자료구조)
•
Element(item): 스택에 삽입되는 원소의 타입
•
maxStackSize: 스택의 최대 크기(양의 정수)
CreateStack 연산
•
크기가 maxStackSize인 빈 스택을 생성하여 반환
Stack CreateStack(maxStackSize)
C
복사
Push 연산
•
item을 스택 top에 삽입
•
스택 가득차 있으면 에러
Stack Push(stack, item)
if (StackIsFull(stack))
then {stackFull 출력;}
else {스택의 가장 위에 item 삽입하고 스택 반환}
C
복사
Pop 연산
•
스택의 top 원소 제거하고 반환
•
스택 비어있으면 에러
Stack Pop(stack)
if (StackIsEmpty(stack))
then {stackEmpty 출력;}
else {스택의 가장 위에 있는 원소를 삭제하고 반환 }
C
복사
StackIsFull
•
현재 원소 개주가 맥스값이면 True 아니면 False
Boolean StackIsFull(stack, maxStackSize)
if (stack의 원소 개수 == maxStackSize)
then {True 반환;}
else {False 반환; }
C
복사
StackIsEmpty
•
스택이 비어있으면 True 아니면 False
Boolean StackIsEmpty(stack)
if (stack == CreateStack(maxStackSize))
then {True 반환;}
else {False 반환; }
C
복사
스택의 구현
생성
#define STACK_SIZE 10 // 최대 크기 정의
typedef int element; // 원소 타입을 int로 정의
element stack[STACK_SIZE]; // 배열을 이용한 스택
int top = -1; // 스택의 초기 상태: 비어 있음
C
복사
•
stack 배열: 실제 데이터를 저장할 공간
•
top 변수: 현재 스택의 맨 위 인덱스를 가리킴 (1은 빈 상태를 의미)
삽입 push
void push(int item) {
if (top >= STACK_SIZE - 1) {
printf("stackFull\n");
} else {
stack[++top] = item; // top을 하나 증가시키고 item 삽입
}
}
C
복사
•
top이 마지막 인덱스에 도달하면 → overflow
•
정상적인 경우 → top을 1 증가시키고 값 저장
삭제 pop
int pop() {
if (top == -1) {
printf("stackEmpty\n");
return -1; // underflow
} else {
return stack[top--]; // 현재 top 값을 반환 후, top을 1 감소
}
}
C
복사
•
top이 1이면 스택이 비어 있으므로 underflow
•
그렇지 않으면 top 위치의 값을 반환하고, top을 1 줄임
보조 연산 (isEmpty / isFull)
int isEmpty() {
return (top == -1);
}
int isFull() {
return (top == STACK_SIZE - 1);
}
C
복사
사칙연산의 중위·전위·후위 표현
수식표기법
•
중위(Infix): 연산자가 피연산자 사이에 위치
A + B
•
전위(Prefix, Polish): 연산자가 앞에 위치
+ A B
•
후위(Postfix, RPN): 연산자가 뒤에 위치
A B +
우리가 보통 쓰는 수식은 중위 표기이나, 컴퓨터가 계산하기에 연산자 우선순위와 괄호 고려하기 복잡함
후위표기는 괄호와 우선순위 고려가 필요 없어 계산 규칙이 단순함
따라서 실제 연산과정에서는 주로 후위 표기식으로 바꿔서 계산
이때 스택을 이용하면 피연산자는 push, 연산자는 pop 후 계산 이라는 단순한 절차로 계산가능
중위 표기 → 후위 표기 변환 규칙
1.
중위 수식을 (피연산자, 연산자, 피연산자) 형태로 괄호로 묶음
2.
괄호 안에서 연산자를 가장 오른쪽으로 이동
3.
다시 (피연산자, 연산자, 피연산자) 묶음 단위를 피연산자로 취급하고 반복
4.
모든 괄호를 제거
(A - (B / C)) - (D * E)
(A - (B C /)) - (D E *)
((A (B C / ) - ) (D E *) - )
A B C / - D E * -
Mathematica
복사
스택을 이용한 후위 표기식 계산 알고리즘
1.
수식을 왼쪽에서 오른쪽으로 읽음
2.
피연산자(숫자) → 스택에 push
3.
연산자 → 필요한 만큼 pop 하여 계산 후 결과를 다시 push
4.
수식 끝까지 반복
5.
마지막에 스택에 남은 값이 최종 결과
예시 계산
후위 수식 3 6 9 * +
1.
3 → 피연산자 → push
Stack: [3]
Makefile
복사
2.
6 → 피연산자 → push
Stack: [3, 6]
Makefile
복사
3.
9 → 피연산자 → push
Stack: [3, 6, 9]
Makefile
복사
4.
* → 연산자 → pop 두 번 (9, 6) → 6 * 9 = 54 → push
Stack: [3, 54]
Makefile
복사
5.
+ → 연산자 → pop 두 번 (54, 3) → 3 + 54 = 57 → push
Stack: [57]
Makefile
복사
→ 최종 결과 57