728x90
01. 스택의 개념과 추상 자료형
✅ 스택
- 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형
- 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현(First In Last Out, LIFO)
- 0개 이상의 원소를 갖는 유한 순서 리스트
- push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조
🔸스택의 추상자료형
- 스택 추상 자료형: 세 개의 연산(create, push, pop)만 해당 객체에 접근 가능하도록 제한하는 것
- 추상 자료형은 운영체제/컴파일러 개발자들이 만드는 것으로 소프트웨어/애플리케이션 개발자들이 다른 연산으로는 객체(데이터)에 접근할 수 없도록 막고, 이를 이용해서 OS나 프로그래밍언어가 효율적으로 작동하게 만듬
▪️ CreateS 연산
Stack CreateS(maxStackSize) ::= 스택의 크키가 maxStackSize인 빈 스택을 생성하고 반환;
▪️ Push 연산
Element Push(stack, item) ::= if( isFull(stack) ) then{ 'stackFull' 출력; }else{ 스택의 가장 위에 item을 삽입하고 스택 반환; }
▪️ Pop 연산
Element Pop(stack) ::= if( IsEmpty(stack) ) then{ 'stackEmpty' 출력; }else{ 스택의 가장 위에 있는 원소를 삭제하고 반환; }
🔸Pop/Push 연산 실행
| ⓡ CreateS(3); ② Push(stack, 'S'); ③ Push(stack, 'T'); ④ Pop('T'); ⑤ Push(stack, 'R'); ⑥ Push(stack, 'P'); ⑦ Push(stack, 'Q'); ⑧ Pop(stack); |
- top: 현재 스택에서 제일 위에 있는 값만을 가리키는 변수로 top을 이용해서만 스택에 접근할 수 있음
02. 스택의 응용과 구현
🔸스택의 다양한 응용
- 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
- 서브루틴 호출 관리를 위한 스택
- 예) main 함수에서 A 함수를 호출하고 A함수에서 B함수를 호출할 경우, B함수 실행 종료 후 돌아가야할 위치, A함수 실행 종료 후 돌아가야할 위치를 저장하는데 스택이 사용됨
- 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
- 인터럽트의 처리와 이후 리턴할 명령 수행 지점을 저장하기 위한 스택
- 컴파일러, 순환 호출(재귀호출) 관리
🔸스택의 삭제 연산
int a = 5;
int b = a--; //b = 5, a = 4
int a = 5;
int b = --a; //b = 4, a = 4- top--에서 사용된 '--' 연산자의 위치에 따라 연산의 적용 순서가 달라질 수 있음
🔸스택의 구현
▪️ 스택의 생성
#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1;
▪️ 스택의 삭제 연산
element pop(){
if(top == -1){
printf("Stack is Empty!\n")
return 0;
}else{
return stack[top--]; //리턴 후, 삭제
}
}
▪️ 스택의 삽입 연산
void push(element item){ //스택의 삽입 연산, item=400
if(top >= STACK_SIZE-1){
printf("Stack is Full!\n");
return;
}eles{
stack[++top] = item;
}
}
03. 사칙 연산식의 전위/후위/중위 표현
📌 컴퓨터가 계산을 하기 위해 혹은 계산을 더 빠르게 하기 위해서 수식을 가지고 있어야 하는데 이는 사람이 사용하는 수식 표현 방법과 다름
🔸수식의 계산
- 연산자의 계산순서를 생각해야 함
- A+B*C+D ▶ ((A+(B*C))+D)
🔸수식의 표기 방법
- 중위 표기법(infix notation)
- 연산자를 피연산자 사이에 표기하는 방법
- A+B
- 전위 표기법(prefix notation)
- 연산자를 피연산자 앞에 표기하는 방법
- +AB
- 후위 표기법(postfix notation)
- 연산자를 피연산자 뒤에 표기하는 방법
- AB+
🔸중위 표기식의 후위 표기식 변환 방법
- 먼저 중위 표기식을 연산자의 우선순위를 고려하여(피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌
- 각 계산 뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킴
- 각 계산 뭉치를 하나의 피연산자로 고려하여 위의 작업을 반복함
- 괄호를 모두 제거함
예)
728x90
'KNOU > 자료구조' 카테고리의 다른 글
| [자료구조] 6. 연결 리스트의 응용 (0) | 2022.11.30 |
|---|---|
| [자료구조] 5. 연결리스트 (0) | 2022.11.28 |
| [자료구조] 4. 큐 (1) | 2022.11.25 |
| [자료구조] 2. 배열 (0) | 2022.11.05 |
| [자료구조] 1. 자료구조의 개념 (0) | 2022.11.04 |
