1. 스택이란?
- 스택은 나중에 들어간 요소가 가장 먼저 나오는 (Last-In, First-Out:LIFO) 자료구조
2. 스택의 주요 기능 : 삽입과 제거
- 삽입(Push)
- 삭제(Pop)
3. 배열로 구현하는 스택
- 스택 구조체의 선언
typedef struct tagArrayStack{ int Capacity; /* 용량 */ int Top; /* 최상위 노드의 위치 */ Node* Nodes; /* 노드 배열 */ } ArrayStack; |
- 스택의 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity) { /* 스택을 자유저장소에 생성 */ (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); /* 입력된 Capacity만큼의 노드를 자유저장소에 생성 */ (*Stack)->Nodes = (Node*)malloc(sizeof(Node)*Capacity); /* Capacity 및 Top 초기화 */ (*Stack)->Capacity = Capacity; (*Stack)->Top = 0; } |
- 스택의 소멸
void AS_DestroyStack(ArrayStack* Stack) { /* 노드를 자유 저장소에서 해제 */ free(Stack->Nodes); /* 스택을 자유 저장소에서 해제 */ free(Stack); } |
- 삽입(Push) 연산
void AS_Push(ArrayStack* Stack, ElementType data) { int Position = Stack->Top; Stack->Nodes(Position)Data = Data; Stack->Top++; } |
- 제거(Pop) 연산
ElementType AS_Pop(ArrayStack* Stack) { int Position = --(Stack->Top); return Stack->Nodes(Position)Data; } |
4. 링크드 리스트로 구현하는 스택
- 노드 구조체
typedef struct tagNode { char* data; struct tagNode* NextNode; } Node; |
- 스택 구조체
typedef struct tagLinkedListStack { Node* List; Node* Top; } LinkedListStack; |
- 삽입(Push) 연산
void LLS_Push(LinkedListSTack* Stack, Node* NewNode) { if(Stack->List == NULL) { Stack->List = NewNode; } else { /* 최상위 노드를 찾아 NewNode를 연결한다.(쌓는다.) */ Node* OldTop = Stack->List; while(OldTop->NextNode != NULL) { OldTop = OldTop ->NextNode; } OldTop->NextNode = NewNode; } /* 스택의 Top 필드에 새 노드의 주소를 등록한다. */ Stack->Top = NewNode; } |
- 삭제(Pop) 연산
Node* LLS_Pop(LinkedListStack* Stack){ /* 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다. */ Node* TopNode = Stack->Top; if(Stack->List == Stack->Top) { Stack->List = NULL; Stack->Top = NULL; } else { /* 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */ Node* CurrentTop = Stack->List; while(CurrentTop != NULL && CurrentTop->NextNode != Stack->Top) { CurrentTop = CurrentTop -> NextNode; } Stack->Top = CurrentTop; CurrentTop->NextNode = NULL; } return TopNode; } |
5. 스택의 응용: 사칙 연산 계산기
- 중위 표기법 : 연산자가 피연산자의 가운데 위치
- 후위 표기법 : 연산자가 피연산자의 뒤에 위치
중위 표기법 |
후위 표기법 |
1 + 3 |
1 3 + |
23 / 7 + 12 |
23 7 / 12 + |
(117.32 + 83) * 49 |
117.32 83 + 49 * |
1 - 3 * 2 |
1 3 2 * - |
- 후위 표기식 계산 알고리즘
- 중위 표기법에서 후위 표기법으로의 변환 알고리즘
+ 입력받은 중위 표기식에서 토큰을 읽는다.
+ 토큰이 피연산자이면 토큰을 결과에 출력한다.
+ 토큰이 연산자(괄호포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다 우선순위가 높으면(왼쪽 괄호는 우선 순위가 가장 낮다.) 스택에 삽입하고, 그렇지 않다면 결과에 출력한다.
+ 토큰이 오른쪽 괄호 ')' 이면 최상위 노드에 왼쪽 괄호'('가 올때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않는다.
+ 중위 표기식에 더 읽을 것이 없다면 빠져나가고, 더 읽을 것이 있다면 1부터 다시 반복한다.
토큰 |
작업 |
출력 |
스택 |
(117.32 + 83) * 49 |
스택에 '(' 삽입 |
|
( |
(117.32 + 83) * 49 |
117.32 출력 |
117.32 |
( |
(117.32 + 83) * 49 |
스택에 '+' 삽입 |
117.32 |
+ ( |
(117.32 + 83) * 49 |
83 출력 |
117.32 83 |
+ ( |
(117.32 + 83) * 49 |
스택의 모든 연산자 제거 후 출력 ('('는 출력 안함) |
117.32 83 + |
|
(117.32 + 83) * 49 |
스택에 '*' 삽입 |
117.32 83 + |
* |
(117.32 + 83) * 49 |
49 출력 |
117.32 83 + 49 |
* |
(117.32 + 83) * 49 |
식 모두 읽었음. 스택의 모든 연산자 제거 후 출력 |
117.32 83 + 49 * |
|
