코딩테스트 및 개인공부/자료구조
[자료구조] [3] 스택
JJPearl
2021. 12. 1. 02:40
반응형
스택
스택은 자료의 입출력이 후입선출(LIFO)의 형태로 일어나는 자료 구조.
스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조.
스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다.
- 스택의 연산
- init() : 스택을 초기화
- is_empty() : 스택이 비어있으면 TRUE, 아니면 FALSE 반환
- is_full() : 스택이 가득 차 있으면 TRUE, 아니면 FALSE 반환
- size(): 스택 내의 모든 요소들의 개수를 반환
- push(x) : 주어진 요소 x를 스택의 맨 위에 추가
- pop() : 스택 맨 위에 있는 요소를 삭제하고 반환
- peek() : 스택 맨 위에 있는 요소를 삭제하지 않고 반환
- 스택의 활용
스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용.
예를 들어 (A,B,C,D,E)의 데이터를 역순으로 하고 싶다면 데이터를 전부 스택에 입력했다가 다시 꺼내면 된다.
- 스택의 주요 활용 분야
- 편집기의 되돌리기(undo) 기능 구현. 되돌리기 기능은 수행된 명령어들 중에서 가장 최근에 수행된 것 부터 순서적으로 취소해야 하기 때문.
- 함수 호출에서 복귀주소를 기억하는데 사용.
복잡한 함수의 호출과 반환을 위해 운영체제는 시스템 스택을 사용, 함수가 호출될 때 마다 활성화 레코드(activation record)를 만들어 스택에 저장.
이 레코드에는 현재 수횡되는 문장의 주소(program counter)가 저장되고, 함수가 끝나면 스택에서 가장 최근의 복귀 주소를 구해서 그곳으로 되돌아간다.
활성화 레코드에는 함수 호출시 매개변수와 함수 안에서 선어된 지역 변수들도 함께 저장된다.
예) main()에서 함수 a()를 호출하고 a()에서 다시 b()와 c()를 연속적으로 호출한 상황
int a() { b(); c(); return 0; } int b() { ... return 0; } int b() { ... return 0; } int main() { a(); return 0; }
- 문서나 소스코드에서 괄호 닫기가 정상적으로 되었는지 검사하는 프로그램, 계산기 프로그램에서 입력된 수식을 계산하는 과정, 미로에서 출구를 찾기에 스택 사용
스택의 구현방법
스택을 구현하는 방법은 배열을 이용한 구현, 연결리스트를 이용한 구현이 있다.
배열을 이용하면 스택을 가장 간단하게 구현 가능, 하지만 용량이 고정되는 단점이 있다.
연결리스트를 이용하면 크기가 제한되지 않는 유연한 리스트를 구현할 수 있다. 그리고 크기의 제한이 없으므로 is_full 연산이 필요 없다.
- 배열을 이용한 스택
정수를 저장할 수 있는 스택을 배열로 구현해보자.
- 정수를 저장하는 스택 표현을 위한 데이터
- 정수 항목들을 저장할 배열 data[MAX_STACK_SIZE], 상수 MAX_STACK_SIZE는 스택에 저장 가능한 최대 요소 개수.
- 변수 top : 가장 최근에 입력된 항목의 위치를 가리키기 위한 변수. 스택 연산의 핵심 변수.
- 공백 상태와 포화 상태 검사
- 공백 상태(is_empty()) : top이 가장 최근에 입력된 항목의 위치이므로, 이 값이 -1이면 스택에는 항목이 하나도 없는 공백상태.
- 포화 상태(is_full()): top이 MAX_STACK_SIZE-1 이면 스택은 포화상태.
- 스택의 초기화와 요소 개수 검사
- 스택 초기화(init()) : 스택을 공백상태로 만드는 것을 의미. top을 -1로 초기화.
- 요소 개수(size()) : 스택의 현재 요소의 개수는 항상 top+1.
- 삽입 연산과 삭제 연산
- 삽입(push()) : is_full()을 통해 포화상태 검사, 아니라면 top을 먼저 하나 증가 후 이 위치에 요소 x를 스택에 삽입. 삽입 연산 후 top은 여전히 가장 최근에 삽입된 요소의 위치를 가리킨다.
- 삭제(pop()) : 스택의 맨 위에 있는 요소(top)를 꺼내서 반환하는 연산. is_empty()를 검사해 스택이 공백인지 검사, 아니라면 top이 가리키는 값을 반환하고 top을 하나 감소.
- peek() : 공백 상태만 검사 후, 맨 위의 항목인 data[top]을 반환. top은 변하지 않는다.
#include <stdio.h>
#define MAX_STACK_SIZE 100 // 스택 요소 저장을 위한 배열의 크기
typedef int Element; // 스택 요소의 자료형 정의
Element data[MAX_STACK_SIZE]; // 실제 스택 요소의 배열
int top; // 실제 스택의 탑
void init_stack() {
top = -1;
}
int is_empty() {
return (top == -1);
}
int is_full() {
return (top == MAX_STACK_SIZE - 1);
}
int size() {
return top + 1;
}
void push(Element e) {
if (!is_full()) {
data[++top] = e;
}
else
printf("스택 포화 상태");
}
Element pop() {
if (!is_empty()) {
return data[top--]; // top이 가리키는 값 반환 후 top 하나 감소
}
else
printf("스택 공백 상태");
}
Element peek() {
if (!is_empty()) {
return data[top];
}
else
printf("스택 공백 상태");
}
void print_stack(const char msg[]) {
printf("%s [size:%2d]= ", msg, size());
for (int i = 0; i < size(); ++i) {
printf("%2d ", data[i]);
}
printf("\n");
}
void main() {
init_stack();
for (int i = 1; i < 10; ++i)
push(i);
print_stack("push 9회 후 ");
printf("pop -> %d\n", pop());
printf("pop -> %d\n", pop());
printf("pop -> %d\n", pop());
print_stack("pop 3회 후 ");
}
스택을 이용한 후위 표기 수식의 계산
- 전위(prefix) 표기법: 연산자를 피연산자 앞에 표기한다. 예) +AB, _5*AB
- 중위(infix) 표기법: 연산자를 피연산자 사이에 표기한다. 예) A+B, 5+A*B
- 후위(postfix) 표기법: 연산자를 피연산자 뒤에 표기한다. 예) AB+, 5AB*+
사람은 중위 표기법에 익숙하지만 컴파일러는 후위 표기법을 좋아한다.
- 후위 표기법의 장점
중위 표기 수식 ( A + B ) * C 는 더하기 연산이 곱하기 연산보다 먼저 수행되어야 함을 나타낸다.
후위 표기식으로 하면 A B + C * 이다. 이 표기법의 장점은
- 괄호를 사용하지 않고 계산해야 할 순서를 알 수 있다.
- 연산자의 우선순위를 생각할 필요가 없다. 식 자체에 우선순위가 이미 포함되어 있다.
- 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식은 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽어야 계산이 가능하다.
컴파일러는 이러한 장점 때문에 입력된 중위 표기 수식을 후위 표기 수식으로 변환해서 계산하는 방법을 사용한다.
- 후위 표기 수식의 계산 알고리즘
- 후위 표기 수식의 계산을 위해 수식을 왼쪽에서 오른쪽으로 스캔하는데, 스캔 과정에서 피연산자가 나오면 무조건 스택에 저장한다.
- 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 연산을 실행,
- 그 결과를 다시 스택에 저장.
- 이 과정을 수식이 모두 처리될 때 까지 반복,
- 마지막에 스택에는 최종 계산 결과 하나만 남는다.
예) 8 2 / 3 - 3 2 * + (중위 표기 수식: 8/2 - 3 + 3*2)
- 피연산자 8, 피연산자 2 : 스택에 순서대로 삽입
- 연산자 / : 스택에서 2와 8 순서대로 꺼내 나누기 연산 후 연산 결과인 8/2=4 를 다시 스택에 삽입
- 피연산자 3 : 스택에 삽입
- 연산자 - : 스택에서 3과 4를 꺼내고 연산 결과인 4-3=1을 스택에 저장
- 피연산자 3, 피연산자 2 : 스택에 순서대로 삽입
- 연산자 * : 스택에서 2와 3을 꺼내고 연산 결과인 3*2=6을 스택에 저장
- 연산자 + : 스택에서 6과 1을 꺼내고, 1+6=7 을 스택에 저장.
- 스택에서 최종 계산 결과 7을 꺼내 반환.
코드
#include <stdio.h>
#define MAX_STACK_SIZE 100 // 스택 요소 저장을 위한 배열의 크기
typedef double Element; // 스택 요소의 자료형 정의
Element data[MAX_STACK_SIZE]; // 실제 스택 요소의 배열
int top; // 실제 스택의 탑
void init_stack() {
top = -1;
}
int is_empty() {
return (top == -1);
}
int is_full() {
return (top == MAX_STACK_SIZE - 1);
}
int size() {
return top + 1;
}
void push(Element e) {
if (!is_full()) {
data[++top] = e;
}
else
printf("스택 포화 상태\n");
}
Element pop() {
if (!is_empty()) {
return data[top--]; // top이 가리키는 값 반환 후 top 하나 감소
}
else
printf("스택 공백 상태\n");
}
Element peek() {
if (!is_empty()) {
return data[top];
}
else
printf("스택 공백 상태\n");
}
void print_stack(const char msg[]) {
printf("%s [size:%2d]= ", msg, size());
for (int i = 0; i < size(); ++i) {
printf("%2d ", data[i]);
}
printf("\n");
}
double calc_postfix(const char expr[]) { // 후위 표기 수식 계산 함수
init_stack();
double num1 = 0, num2 = 0;
for (int i = 0; expr[i] != '\0'; ++i) {
char c = expr[i];
if (c >= '0' && c <= '9') {
push(expr[i] - '0'); // int형으로 변환해서 push
}
else if(c == '+' || c == '-' || c == '/' || c == '*'){ // 연산자라면
num2 = pop();
num1 = pop();
switch (c) {
case '+':
push(num1 + num2);
break;
case '-':
push(num1 - num2);
break;
case '/':
if(num2 != 0)
push(num1 / num2);
break;
case '*':
push(num1 * num2);
break;
}
}
}
return pop();
}
void main() {
char expr[2][40] = { "8 2 / 3 - 3 2 * +", "1 2 / 4 * 1 4 / *" };
printf("후위 표기 수식[1]:%s = %lf\n", expr[0], calc_postfix(expr[0]));
printf("후위 표기 수식[2]:%s = %lf\n", expr[1], calc_postfix(expr[1]));
}
스택을 이용해 중위 표기 수식을 후위 표기로 변환
- 중위 표기의 후위 표기 변환 알고리즘
두 표기식의 공통점은 피연산자의 순서가 동일하다는 것.
연산자의 출력 순서는 연산자들의 우선 순위 관계와 괄호에 의해 결정.
- 중위 표기 수식을 순서대로 스캔
- 피연산자를 만나면 바로 (후위 표기식으로) 출력
- 연산자를 만나면 스택에 저장. 후위 표기는 연산자가 피연산자 뒤에 나오므로 적절한 위치를 찾을 때 까지 출력을 보류.
- 연산자 우선순위를 고려해 출력하는 방법
- 현재 연산자보다 우선순위가 높거나 같은 연산자는 모두 연산자 스택에서 출력한 후 현재 연산자를 스택에 넣는다. 예) 연산자 스택에 +가 들어있고, 현재 스캔한 연산자가 * 라면 + 위에 * 삽입
- 우선순위가 같은 경우도 먼저 출력. 우선순위가 같은 연산자는 먼저 나온 연산자가 먼저 처리 되어야 하므로. 예) a-b+c같은 경우 abc+-로 출력한다면 문제 발생
- 입력 수식이 끝나면 스택의 남은 연산자들을 모두 pop()해서 후위 표기식으로 출력한다.
- 괄호 처리 방법
- 왼쪽 괄호는 무조건 스택에 삽입. 왼쪽 괄호가 스택에 삽입되면 왼쪽 괄호를 제일 우선순위가 낮은 연산자로 취급. 즉, 다음에 만나는 어떤 연산자도 스택에 삽입 된다.
- 오른쪽 괄호를 만나면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호위에 쌓여있는 모든 연산자들을 출력.
- 단, 괄호는 후위표기식에 출력하지 않는다.
코드
... // 정수 스택 배열로 구현한 코드에 추가
int precedence(char oper) { // 연산자 우선순위 반환 함수
switch (oper)
{
case '(': case ')':
return 0;
case '+': case '-':
return 1;
case '/': case '*':
return 2;
}
}
void infix_to_postfix(const char expr[]) { // 중위 수식 -> 후위 표기 함수
init_stack();
char oper;
for (int i = 0; expr[i] != '\0'; ++i) {
char c = expr[i];
if (c >= '0' && c <= '9') {
printf("%c", c);
}
else { // 연산자라면
switch (c)
{
case '(':
push(c);
break;
case ')':
while (!is_empty()) {
oper = pop();
if (oper == '(')
break;
else
printf("%c", oper);
}
break;
case '+': case '-': case '/': case '*':
while (!is_empty()) { // 연산자 스택이 empty가 아니라면
oper = peek(); // 스택의 top
if (precedence(c) <= precedence(oper)) {// 현재 연산자가 스택의 top 연산자 보다 우선순위가 낮다면
oper = pop();
printf("%c", oper);
}
else
break;
}
push(c); // 현재 연산자인 c를 push
break;
}
}
}
while (!is_empty()) {
printf("%c", pop());
printf("\n");
}
}
void main() {
char expr[2][40] = { "8 / 2 - 3 + (3 * 2)", "1 / 2 * 4 * (1 / 4)" };
printf("중위 수식:%s --> 후위 수식:", expr[0]);
infix_to_postfix(expr[0]);
printf("중위 수식:%s --> 후위 수식:", expr[1]);
infix_to_postfix(expr[1]);
}
반응형