-
스택 주차장의 추억
'가장 먼저 들어간 데이터가 가장 마지막에 나오는 구조'
스택은 뭔가를 쌓아놓은 '더미'를 뜻함
LIFO(Last In, First Out)
요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징
-
스택의 주요 기능 : 삽입과 제거
스택의 주요 기능은 '삽입(push)'와 '제거(pop)'
-
배열로 구현하는 스택
스택과 스택의 노드 표현하기
-
노드
typedef int ElementType;
typedef struct tagNode
{
ElementType data;
} NODE;
-
스택 구조체
typedef struct tagArrayStack
{
int capacity; // 용량
int top; // 최상위 노드의 위치
NODE* node; // 노드 배열
} ArrayStack;
노드 배열을 자유 저장소에 할당하고 NODE포인터는 아래 그림과 같이 자유 저장소에 할당된 배열을 가리키는데 사용될 것이다.
스택의 기본 연산 구현하기
-
스택의 생성
void AS_createStack(ArrayStack** stack, int capacity)
{
// 스택을 자유 저장소에 생성
(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
// 입력된 capacity만큼의 노드를 자유 저장소에 생성
(*stack)->node = (NODE*)malloc(sizeof(NODE)*capacity);
// 초기화
(*stack)->capacity = capacity;
(*stack)->top = 0;
}
-
스택의 소멸
void AS_destroyStack(ArrayStack *stack)
{
// 노드를 자유 저장소에서 해제
free(stack->node);
// 스택을 해제
free(stack);
-
삽입(push) 연산
void AS_push(ArrayStack *stack, ElementType data)
{
int position = stack->top;
stack->node[position].data = data;
stack->top++;
}
-
제거(pop) 연산
ElementType AS_pop(ArrayStack *stack)
{
int position = --(stack->top);
return stack->node[position].data;
}
배열로 구현하는 스택 예제 프로그램
- 예제 ArrayStack.h
-
|
#ifndef ARRAYSTACK_H__ #define ARRAYSTACK_H__
typedef int ElementType;
typedef struct tagNode { ElementType data; } NODE;
typedef struct tagArrayStack { int capacity; int top; NODE* node; } ArrayStack;
void AS_createStack(ArrayStack **stack, int capacity); void AS_destroyStack(ArrayStack *stack); void AS_push(ArrayStack *stack, ElementType data); ElementType AS_pop(ArrayStack *stack); ElementType AS_top(ArrayStack *stack); int AS_getSize(ArrayStack *stack); int AS_isEmpty(ArrayStack *stack);
#endif |
- 예제 ArrayStack.c
|
#include "stdafx.h" #include "ArrayStack.h"
void AS_createStack(ArrayStack **stack, int capacity) { // 스택을 자유 저장소에 생성 (*stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); // capacity만큼 동적할당 (*stack)->node = (NODE*)malloc(sizeof(NODE) * capacity);
// 초기화 (*stack)->capacity = capacity; (*stack)->top = 0; } void AS_destroyStack(ArrayStack *stack) { // 노드 해제 free(stack->node); // 스택 해제 free(stack); } void AS_push(ArrayStack *stack, ElementType data) { int position = stack->top;
stack->node[position].data = data; stack->top++; } ElementType AS_pop(ArrayStack *stack) { int position = --(stack->top);
return stack->node[position].data ; } ElementType AS_top(ArrayStack *stack) { int position = stack->top - 1; return stack->node[position].data; } int AS_getSize(ArrayStack *stack) { return stack->top; } int AS_isEmpty(ArrayStack *stack) { return ( stack->top == 0 ); } |
- 예제 main.c
|
// 02_ArrayStack.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. //
#include "stdafx.h" #include "ArrayStack.h"
int _tmain(int argc, _TCHAR* argv[]) { int i = 0 ; ArrayStack* stack = NULL;
AS_createStack(&stack, 10);
AS_push(stack, 3); AS_push(stack, 37); AS_push(stack, 11); AS_push(stack, 12);
printf("capacity : %d, size : %d, top : %d\n", stack->capacity, AS_getSize(stack), AS_top(stack));
for( i = 0 ; i < 4 ; i++ ) { if( AS_isEmpty(stack) ) break;
printf("popped : %d, ", AS_pop(stack));
if( !AS_isEmpty(stack) ) printf("current top : %d\n", AS_top(stack)); else printf("stack is empty\n"); }
AS_destroyStack(stack); return 0; } |
-
링크드 리스트로 구현하는 스택
스택과 스택의 노드 표현하기
-
링크드 리스트 스택 노드
typedef struct tagNode
{
char* data;
struct tagNode* next;
} NODE;
-
링크드 리스트 스택 구조체
typedef struct tagLinkedListStack
{
NODE* list;
NODE* top;
} LinkedListStack;
스택의 기본 연산 구현하기
-
스택의 생성
NODE* LLS_createNode(char* newData)
{
// 노드 할당
NODE* newNode = (NODE*)malloc(sizeof(NODE));
// 입력 받은 문자열의 크기만큼 data할당
newNode->data = (char*)malloc(strlen(newData)+1);
// 초기화
newNode->Next = NULL;
return newNode;
}
-
스택의 소멸
void LLS_destroyNode(NODE* node)
{
free(node->data);
free(node);
}
-
삽입(push) 연산
void LLS_push(LinkedListStack* stack, NODE* newNode)
{
if( stack->list == NULL )
{
stack->list = newNode;
}
else
{
// 최상위 노드를 찾아 newNode를 연결(쌓기)
NODE* oldTop = stack->list;
while( oldTop->next != NULL )
{
oldTop = oldTop->next;
}
oldTop->next = newNode;
}
// 스택의 top필드에 새 노드의 주소를 등록
stack->top = newNode;
}
- 제거(pop) 연산
- 현재 최상위 노드의 주소를 다른 포인터에 복사
- 새로운 최상위 노드, 즉 현재의 최상위 노드 이전 노드 찾기
- LinkestListStack 구조체의 top 필드에 새로운 최상위 노드의 주소 등록
-
1에서 포인터에 저장해둔 옛 최상위 노드의 주소 반환
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->next != stack->top )
{
currentTop = currentTop->next;
}
stack->top = currentTop;
currentTop->next = NULL;
}
return topNode;
}
링크드 리스트로 구현하는 스택 예제 프로그램
- 예제 LinkedListStack.h
-
|
#ifndef LINKEDLISTSTACK_H__ #define LINKEDLISTSTACK_H__
typedef struct tagNode { char* data; struct tagNode* next; } NODE;
typedef struct tagLinkedListStack { NODE* list; NODE* top; } LinkedListStack;
void LLS_createStack(LinkedListStack** stack); void LLS_destroyStack(LinkedListStack* stack);
NODE* LLS_createNode(char* data); void LLS_destroyNode(NODE* node);
void LLS_push(LinkedListStack* stack, NODE* newNode); NODE* LLS_pop(LinkedListStack* stack);
NODE* LLS_top(LinkedListStack* stack); int LLS_getSize(LinkedListStack* stack); int LLS_isEmpty(LinkedListStack* stakc);
#endif |
- 예제 LinkedListStack.c
|
#include "stdafx.h" #include "LinkedListStack.h"
void LLS_createStack(LinkedListStack** stack) { // 스택을 자유저장소에 생성 (*stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack)); // 초기화 (*stack)->list = NULL; (*stack)->top = NULL; } void LLS_destroyStack(LinkedListStack* stack) { while( !LLS_isEmpty(stack) ) { // 데이터 저장소 해제 NODE* popped = LLS_pop(stack); LLS_destroyNode(popped); } // 스택 해제 LLS_destroyNode(stack); }
NODE* LLS_createNode(char* data) { NODE* newNode = (NODE*)malloc(sizeof(NODE)); newNode->data = (char*)malloc(strlen(data)+1);
// 데이터 저장 strcpy(newNode->data, data); // 다음 노드 포인터 NULL초기화 newNode->next = NULL;
return newNode; } void LLS_destroyNode(NODE* node) { free(node->data); free(node); }
void LLS_push(LinkedListStack* stack, NODE* newNode) { if( stack->list == NULL ) { stack->list = newNode; } else { // 최상위 노드를 찾아 연결 NODE* oldTop = stack->list; while( oldTop->next != NULL ) { oldTop = oldTop->next; } oldTop->next = newNode; } // stack에 top필드에 새 노드 주소 등록 stack->top = newNode; } NODE* LLS_pop(LinkedListStack* stack) { // LLS_pop()함수가 반환할 최상위 노드 NODE* top = stack->top;
if( stack->list == stack->top ) { stack->list = NULL; stack->top = NULL; } else { // 새로운 최상위 노드를 top에 등록 NODE* current = stack->list; while( current != NULL && current->next != stack->top ) { current = current->next; } stack->top = current; currnt->next = NULL; } return top; }
NODE* LLS_top(LinkedListStack* stack) { return stack->top; } int LLS_getSize(LinkedListStack* stack) { int count = 0; NODE* current = stack->list;
while(current != NULL) { current = current->next; count++; } return count; } int LLS_isEmpty(LinkedListStack* stakc) { return (stack->list == NULL); } |
- 예제 main.c
|
// 02_LinkedListStack.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. //
#include "stdafx.h" #include "LinkedListStack.h"
int _tmain(int argc, _TCHAR* argv[]) { int i = 0 ; int count = 0; NODE* pop; LinkedListStack* stack;
LLS_createStack(&stack);
LLS_push(stack, LLS_createNode("abc")); LLS_push(stack, LLS_createNode("def")); LLS_push(stack, LLS_createNode("efg")); LLS_push(stack, LLS_createNode("hij"));
count = LLS_getSize(stack); printf("size : %d, top : %s\n\n", count, LLS_top(stack)->data);
for( i = 0 ; i < count ; i++ ) { if(LLS_isEmpty(stack)) break;
pop = LLS_pop(stack); printf("pop:%s, ", pop->data); LLS_destroyNode(pop);
if( !LLS_isEmpty(stack) ) { printf("current top : %s\n", LLS_top(stack)->data); } else { printf("stack empty\n"); } }
LLS_destroyStack(stack); return 0; } |
-
스택의 응용 : 사칙 연산 계산기
수식의 중위 표기법과 후위 표기법
후위 표기법은 역 폴리쉬 표기법(Reverse Polish Notation)이라고 하는데 호주의 찰스 햄블린(Charles Hamblin)이 1950년대 중반에 개발한 알고리즘이다.
|
중위 표기법 |
후위 표기법 |
|
1 + 3 |
1 3 + |
|
23 / 7 + 12 |
23 7 / 12 + |
|
(117.32 + 83 ) * 49 |
117.32 83 + 49 * |
|
1 - 3 * 2 |
1 3 2 * - |
후위 표기식을 계산하는 알고리즘
후위 표기식을 계산하는 알고리즘은 두 가지 규칙으로 이루어져 있습니다.
ex) '1 3 2 * -'(중위 표기법 : 1 - 3 * 2)의 계산
-
식의 왼쪽부터 요소를 읽어 내면서 피연산자는 스택에 담는다
-
연산자가 나타난 경우 스택에서 피연산자 두 개를 꺼내 연산을 실행하고, 그 결과를 다시 스택에 삽입
이렇게 해서 식을 모두 읽었고 스택에는 식의 최종 계산결과만 남음
-
후위 표기식 알고리즘
double calculate(char* PostfixExpression)
{
/* ... 스택 생성 */
while(PostfixExpression을 끝까지 다 읽을 때까지)
{
/* PostfixExpression에서 토큰을 읽어내고, 읽은 토큰 크기를 read에 누적*/
read += getNextToken(&PostfixExpression[position], token, &type);
/* ... */
if(type == OPERAND) // 토큰이 피연산자면 스택에 삽입
{
LLS_push(&stack, LLS_createNode(token));
}
else // 토큰이 연산자라면 스택의 피연산자들과 함께 계산
{
Operator2 = LLS_pop(&stack);
Operator1 = LLS_pop(&stack);
switch(type) // 연산자 종류에 따라 계산
{
case PLUS: result = Operator1 + operator2; break;case MINUS: result = Operator1 - operator2; break;
case MULTIPLY result = Operator1 * operator2; break;
case DIVIDE: result = Operator1 / operator2; break;
}
LLS_push(&stack, LLS_createNode(result));
}
}
// 스택에 가장 마지막에 남아있는 결과값을 result에 저장
result = LLS_pop(&stack);
/* ... 스택 소멸*/
return result;
}
-
중위 표기법에서 후위 표기법으로의 변환 알고리즘
애드거 다익스트라(Edsger Dijkstra)가 고안한 알고리즘
- 입력받은 중위 표기식에서 토큰을 읽는다
- 토큰이 피연산자이면 토큰을 결과에 출력
- 토큰이 연산자(괄호 포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다 우선순위가 높으면(왼쪽 괄호는 우선순위가 가장 낮음) 스택에 삽입, 그렇지 않으면 결과에 출력
- 토큰이 오른쪽 괄호 ')'이면 최상위 노드에 왼쪽 괄호 '('가 나올때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지 않는다.
- 중위 표기식에서 더 읽을 것이 없다면 빠져나가고, 더 읽을 것이 있다면 1부터 다시 반복
-
|
토큰 |
작업 |
출력 |
스택 |
|
( 117.32 + 83 ) * 49 |
스택에 ( 삽입 |
|
( |
|
117.32 + 83 ) * 49 |
117.32 출력 |
117.32 |
( |
|
+ 83 ) * 49 |
스택에 + 삽입 |
117.32 |
+ |
|
83 ) * 49 |
83 출력 |
117.32 83 |
+ |
|
) * 49 |
스택에 모든 연산자 제거 후 출력 (는 출력 안함 |
117.32 83 + |
|
|
* 49 |
스택에 * 삽입 |
117.32 83 + |
* |
|
49 |
식 모두 읽음 스택에 모든 연산자 제거 후 출력 |
117.32 83 + 49 * |
|
-
다익 스트라의 중위-후위 표기 변환 알고리즘을 구현한 함수
// 첫번째 인자 : 중위 표기식, 두번째 인자 : 후위 표기식
void getPostfix(char* InfixExpression, char* postfixExpression)
{
LinkedListStack* stack;
char token[32];
int type = -1;
unsigned int postion = 0;
unsigned int length = strlen(InfixExpression);
LLS_createStack(&stack);
// 중위 표기식을 다 읽을 때까지
while( position < length )
{
position += getNextToken( &InfixExpression[position, token, &type);
// 토큰이 피연산자라면 후위 표기식에 출력
if( type == OPERAND )
{
strcat(PostfixExpression, token);
strcat(PostfixExpression, " ");
}
else if( type == RIGHT_PARENTHESIS )
{
// 토큰이 오른쪽 괄호라면 왼쪽괄호가 나타날때까지 스택의 노드 제거
while( !LLS_isEmpty(stack) )
{
NODE* pop = LLS_pop(&stack);
if( pop->data[0] == LEFT_PARENTHESIS )
{
LLS_destroyNode(pop);
break;
}
// 토큰이 연산자인 경우
else
{
strcat(PostfixExpression, pop->data);
LLS_destroyNode(pop);
}
}
}
else
{
while( !LLS_isEmpty(stack) && !isPrior(token[0], LLS_top(stack)->data[0]))
{
NODE* pop = LLS_pop(&stack);
if( pop->data[0] != LEFT_PARENTHESIS)
{
strcat(PostfixExpression, pop->data);
LLS_destroyNode(pop);
}
LLS_push(&stack, LLS_createNode(token));
}
}
// 중위 표기식을 다 읽었으니 stack에 남겨진 모든 연산자를 후위식 표기식에 출력
while(!LLS_isEmpty(stack))
{
NODE* pop = LLS_pop(&stack);
if( pop->data[0] != LEFT_PARENTHESIS)
strcat(PostfixExpression, pop->data);
LLS_destroyNode(pop);
}
LLS_destroyStack(stack);
}
사칙 연산 계산기 예제 프로그램
- 예제 calculator.h
|
#ifndef CALCULATOR_H__ #define CALCULATOR_H__
#include <stdlib.h> #include "LinkedListStack.h"
typedef enum { LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS = ')', PLUS = '+', MINUS = '-', MULTIPLY = '*', DIVIDE = '/', SPACE = ' ', OPERAND } SYMBOL;
int isNumber(char cipher); unsigned int getNextToken(char* expression, char* token, int* type); int isPrior(char operator1, char operator2); void getPostfix(char* infixExpression, char* postfixExpression); double calculate(char* postfixExpression); int getPriority(char Operator, int inStack);
#endif |
- 예제 calculator.c
|
#include "calculator.h"
char NUMBER[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.'};
int isNumber(char cipher) { int i = 0; int arrLength = sizeof(NUMBER);
for( i = 0; i < arrLength ; i++ ) { if( cipher == NUMBER[i] ) return 1; } return 0; } unsigned int getNextToken(char* expression, char* token, int* type) { unsigned int i = 0;
for( i = 0 ; 0 != expression[i] ; i++ ) { token[i] = expression[i]; // 피연산자이면 if( isNumber(expression[i]) == 1 ) { *type = OPERAND;
if(isNumber(expression[i+1]) != 1 ) break; } // 연산자이면 else { *type = expression[i]; break; } } token[++i] = '\0'; return i; } int getPriority(char Operator, int inStack) { int priority = -1;
switch(Operator) { case LEFT_PARENTHESIS: if(inStack) priority = 3; else priority = 0; break; case MULTIPLY: case DIVIDE: priority = 1; break; case PLUS: case MINUS: priority = 2; break; } return priority; } int isPrior(char operator1, char operator2) { return (getPriority(operator1, 1) > getPriority(operator2, 0) ); } void getPostfix(char* infixExpression, char* postfixExpression) { LinkedListStack* stack;
char token[32]; int type = -1; unsigned int position = 0; unsigned int length = strlen(infixExpression);
LLS_createStack(&stack);
while( position < length ) { position += getNextToken(&infixExpression[position], token, &type);
if(type == OPERAND) { strcat(postfixExpression, token); strcat(postfixExpression, " "); } else if(type == RIGHT_PARENTHESIS) { while( !LLS_isEmpty(stack) ) { NODE* pop = LLS_pop(stack);
if( pop->data[0] == LEFT_PARENTHESIS ) { LLS_destroyNode(pop); break; } else { strcat(postfixExpression, pop->data); LLS_destroyNode(pop); } } } else { while(!LLS_isEmpty(stack) && !isPrior(LLS_top(stack)->data[0], token[0])) { NODE* pop = LLS_pop(stack);
if( pop->data[0] != LEFT_PARENTHESIS ) strcat(postfixExpression, pop->data);
LLS_destroyNode(pop); }
LLS_push(stack, LLS_createNode(token)); } }
while( !LLS_isEmpty(stack) ) { NODE* pop = LLS_pop(stack);
if( pop->data[0] != LEFT_PARENTHESIS ) strcat(postfixExpression, pop->data);
LLS_destroyNode(pop); } LLS_destroyStack(stack); } double calculate(char* postfixExpression) { LinkedListStack* stack; NODE* resultNode;
double result; char token[32]; int type = -1; unsigned int read = 0; unsigned int length = strlen(postfixExpression);
LLS_createStack(&stack);
while( read < length ) { read += getNextToken(&postfixExpression[read], token, &type);
if( type == SPACE ) continue;
if( type == OPERAND ) { NODE* newNode = LLS_createNode(token); LLS_push(stack, newNode); } else { char resultString[32]; double operator1, operator2, tempResult; NODE* operatorNode;
operatorNode = LLS_pop(stack); operator2 = atof(operatorNode->data); LLS_destroyNode(operatorNode);
operatorNode = LLS_pop(stack); operator1 = atof(operatorNode->data); LLS_destroyNode(operatorNode);
switch(type) { case PLUS: tempResult = operator1 + operator2; break; case MINUS: tempResult = operator1 - operator2; break; case MULTIPLY: tempResult = operator1 * operator2; break; case DIVIDE: tempResult = operator1 / operator2; break; }
// 문자열로 되어 있는 계산 결과를 소수로 변환 gcvt(tempResult, 10, resultString); LLS_push(stack, LLS_createNode(resultString)); } }
resultNode = LLS_pop(stack); result = atof(resultNode->data); LLS_destroyNode(resultNode);
LLS_destroyStack(stack);
return result; } |
- 예제 main.c
|
#include "calculator.h"
void main() { char infixExpression[100]; char postfixExpression[100];
double result = 0.0;
memset(infixExpression, 0, sizeof(infixExpression)); memset(postfixExpression, 0, sizeof(postfixExpression));
printf("Enter Infix Expression:"); scanf("%s", infixExpression);
getPostfix(infixExpression, postfixExpression);
printf("infix:%s\npostfix:%s\n", infixExpression, postfixExpression);
result = calculate(postfixExpression);
printf("Calculation Result : %f\n", result); } |