[자료구조] 스택 (Stack)
1) 스택(Stack)
- 들어온 시간 순으로 데이터를 쌓아갈 때 가장 위(가장 최근에 삽입)에 있는 데이터를 삭제하거나 새로운 데이터를 삽입할 수 있도록 하는 추상 자료형
- 후입선출
- 접근 삽입 및 삭제
- 스택 탑만 접근 가능
- 한쪽 끝에서 삽입, 삭제
- 삽입, 삭제 위치를 스택 탑 부근으로 제한
- 구현 자료구조에서 탑이 아닌 다른 곳을 접근할 수 있어도 하지 않기로 약속
Push 연산
- 스택에서의 삽입 연산
- 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가
- 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우(Overflow) 상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료
- 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입
push(S, x)
{
top = top + 1; // 1
if (top > stack_SIZE) // 2
overflow;
else
S(top) = x; // 3
}
pop 연산
- 스택에서의 삭제 연산
- 스택이 공백 스택이 아니라면 top이 가리키는 원소를 먼저 반환
- 스택의 top 원소를 반환하였으므로 top의 위치는 그 아래의 원소로 변경하기 위해 top의 위치를 하나 감소
pop(S)
{
if (top == 0)
underflow;
else // 1
{
return S(top--); // 2
}
}
2) 배열로 구현한 스택
- 스택의 크기 : 배열의 크기
- 스택에 저장된 원소의 순서 : 배열 원소의 인덱스
- index = 0 : 스택의 첫번째 원소
- index = n-1 : 스택의 n번째 원소
- 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장
- top = -1 : 공백 상태(초기값)
- top = n-1 : 포화 상태
장단점
- 장점 : 순차 자료구조인 1차원 배열을 사용하여 쉽게 구현
- 단점 : 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움
#include<stdio.h>
#include<stdlib.h>
#define STACK_SIZE 100
typedef int element; // int를 스택 element의 자료형으로 정의
element stack[STACK_SIZE];
int top = -1;
void push(element item) // 요소 삽입
{
if (top >= STACK_SIZE - 1)
{
printf("\n\n Stack is FULL \n");
return;
}
else stack[++top] = item;
}
element pop() // 요소 반환
{
if (top == -1)
{
printf("\n\n Stack is Empty \n");
return 0;
}
else return stack[top--];
}
void del() // 리턴 없이 요소 제거
{
if (top == -1)
{
printf("\n\n Stack is Empty \n");
exit(1);
}
else top--;
}
element peek() // 원소 검색
{
if (top == -1)
{
printf("\n\n Stack is Empty \n");
return 0;
}
else return stack[top];
}
void printStack()
{
int i;
printf("\n STACK [ ");
for (i = 0; i <= top; i++)
printf("%d ", stack[i]);
printf("] ");
}
void main()
{
element item;
printStack();
push(1);
printStack();
push(2);
printStack();
push(3);
printStack();
item = peek();
printStack();
printf("peek top => %d", item);
del();
printStack();
item = pop();
printStack();
printf("\t pop top => %d", item);
return;
}
3) 단순 연결 리스트로 구현한 스택
- 스택의 원소 : 단순 연결 리스트의 노드
- 스택 원소의 순서 : 노드의 링크 포인터로 연결
- push : 리스트의 마지막에 노드 삽입
- pop : 리스트의 마지막 노드 삭제
- 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수
- 초기 상태 : top = null
장단점
- 장점 : 동적 메모리로 메모리를 효율적으로 사용
- 단점 : 구현과 이해가 어려움
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int element;
typedef struct stackNode
{
element data;
stackNode* link;
}stackNode;
stackNode* top;
void push(element item) // 요소 삽입
{
stackNode* temp = (stackNode*)malloc(sizeof(stackNode));
temp->data = item;
temp->link = top;
top = temp;
}
element pop() // 요소 반환
{
element item;
stackNode* temp = top;
if (top == NULL)
{
printf("\n\n Stack is empty \n");
return 0;
}
else
{
item = temp->data;
top = temp->link;
free(temp);
return item;
}
}
void del() // 리턴 없이 요소 제거
{
stackNode* temp;
if (top == NULL)
{
printf("\n\n Stack is empty \n");
}
else
{
temp = top;
top = top->link;
free(temp);
}
}
element peek() // 원소 검색
{
element item;
if (top == NULL)
{
printf("\n\n Stack is Empty \n");
return 0;
}
else
{
item = top->data;
return item;
}
}
void printStack()
{
stackNode* p = top;
printf("\n STACK [ ");
while (p)
{
printf("%d ", p->data);
p = p->link;
}
printf("] ");
}
void main()
{
element item;
top = NULL;
printStack();
push(1);
printStack();
push(2);
printStack();
push(3);
printStack();
item = peek();
printStack();
printf("peek top => %d", item);
del();
printStack();
item = pop();
printStack();
printf("\t pop top => %d", item);
return;
}
4) 스택의 응용
괄호 검사
- 수식에 포함되어 있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어 있음
- 후입선출 구조의 스택을 이용하여 괄호를 검사함
- 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사
- 왼쪽 괄호를 만나면 스택에 Push
- 오른쪽 괄호를 만나면 스택을 Pop하여 마지막에 저장한 괄호와 같은 종류인지를 확인
- 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임
- 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨
- 수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임
int testPair(const char* exp)
{
char symbol, open_pair;
int i, length = strlen(exp);
top = NULL;
for (i = 0; i < length; i++)
{
symbol = exp[i];
switch (symbol)
{
case '(':
case '{':
case '[':
push(symbol); break;
case ')':
case '}':
case ']':
if (top == NULL) return 0;
else
{
open_pair = pop();
if ((open_pair == '(' && symbol != ')') ||
(open_pair == '{' && symbol != '}') ||
(open_pair == '[' && symbol != ']'))
return 0;
else break;
}
}
}
if (top == NULL) return 1;
else return 0;
}
void main()
{
const char* express = "{(A + B) - 3}*5 + [{cos(x + y) + 7} - 1] * 4";
printf("%s", express);
if (testPair(express) == 1)
printf("\n\n 수식의 괄호가 맞게 사용되었습니다.");
else
printf("\n\n 수식의 괄호가 틀렸습니다.");
return;
}
수식의 표기법 변환
- 전위 표기법
- 연산자를 피연산자를 앞에 표기하는 방법
- 예) +AB
- 중위 표기법
- 연산자를 피연산자의 가운데 표기하는 방법
- 예) A+B
- 후위 표기법
- 연산자를 피연산자의 뒤에 표기하는 방법
- 예) AB+
- 전위 표기식으로 변환하기
- 수식의 각 연산자에 대해서 우선 순위에 따라 괄호를 사용하여 다시 표현함
- 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킴
- 수식의 괄호를 제거함
- A*B-C/D
- 1단계 : ( (A*B) - (C/D) )
- 2단계 : -( *(AB) / (CD) )
- 3단계 : -*AB / CD
- 후위 표기식으로 변환하기
- 수식의 각 연산자에 대해서 우선 순위에 따라 괄호를 사용하여 다시 표현함
- 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킴
- 수식의 괄호를 제거함
- 알고리즘
- 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽음
- 피연산자(숫자)를 만나면 출력함
- 연산자를 만나면 스택에 Push함
- 오른쪽 괄호를 만나면 스택을 Pop하여 출력함
- 수식이 끝나면, 스택이 공백이 될 때까지 Pop하여 출력함
Infix_to_postfix(exp)
{
while(true)
{
symbol = getSymbol(exp);
if(symbol == operand) // 2
print(symbol);
if(symbol == operator) // 3
push(stack, symbol);
if(symbol == ')') // 4
print(pop(stack));
if(symbol == null) // 5
while(top > -1)
print(pop(stack));
}
}
후위 표기식 연산
- 피연산자(숫자)를 만나면 스택에 Push함
- 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 Pop하여 연산하고, 연산 결과를 다시 스택에 Push함
- 수식이 끝나면, 마지막으로 스택을 Pop하여 출력함
element evalPostfix(const char* exp)
{
int opr1, opr2, value, i = 0;
int length = strlen(exp);
char symbol;
top = NULL;
for (i = 0;i < length;i++)
{
symbol = exp[i];
if (symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/')
{
value = symbol - '0';
push(value);
}
else
{
opr2 = pop();
opr1 = pop();
switch (symbol)
{
case '+': push(opr1 + opr2); break;
case '-': push(opr1 - opr2); break;
case '*': push(opr1 * opr2); break;
case '/': push(opr1 / opr2); break;
}
}
}
return pop();
}
void main()
{
int result;
const char* express = "35*62/-";
printf("후위표기식 : %s", express);
result = evalPostfix(express);
printf("\n\n 연산결과 => %d", result);
return;
}
