스택은 가장 먼저 들어간 데이터가 나중에 나오는 구조로 되어있다. 이를 FILO(First In, Last Out)이라 부른다. 스택의 주요 기능은 '삽입(Push)과 제거(PoP)' 두 가지 뿐이다. 다른 건 다 부수 기능일 뿐이다.
스택은 링크드 리스트와 배열을 통해서 구현할 수 있는데, 먼저 쉬운 난이도의 배열로 구현해보겠다.
배열로 스택 구현하기
typedef int ElementType;
struct Node
{
int data;
};
struct StackArray
{
int capacity; // 용량.
int top; // 최상위 노드 위치.
Node* nodes; // 노드 배열.
};어떤 자료형이 들어올지 모르니, 일단은 int형을 typedef해주었다. 사실 템플릿으로 만들면 더 좋다. capacity를 통해 스택이 가질 수 있는 총량을 알 수 있다. top으로 노드 삽입 / 제거 시에 최상위 노드로 접근할 수 있다. noeds는 말 그대로 노드 배열이다. 포인터니 힙(heap)공간에 저장하겠다는 뜻이다.
스택 생성 / 소멸
void SA_CreateStack(StackArray** stack, int capacity)
{
*stack = new StackArray;
(*stack)->nodes = new Node[capacity];
(*stack)->capacity = capacity;
(*stack)->top = 0;
}
void SA_DestroyStack(StackArray* stack)
{
delete[] stack->nodes;
delete stack;
}nodes는 당연히 배열로 동적 할당해야 될 뿐만 아니라, 스택 구조체 자체도 동적 할당 해주었다. 이를 통해 더 효율적인 메모리 관리가 가능하다. 반대로 파괴할 때는, nodes 먼저 해주었다. 배열인 것을 주의하자.
삽입 / 제거
top 멤버만 관리 잘 해주면 어려울 것 없다.
void SA_Push(StackArray* stack, ElementType data)
{
if (stack->capacity == stack->top)
return;
else
{
stack->nodes[stack->top].data = data;
stack->top++;
}
}
ElementType SA_Pop(StackArray* stack)
{
stack->top--;
return stack->nodes[stack->top--].data;
}그 외 나머지 간단한 함수들도 구현하였다. 그 후 함수들을 이리저리 사용해보면서 에러가 나는지 본다.
ElementType SA_Top(StackArray* stack)
{
return stack->nodes[stack->top - 1].data;
}
int SA_GetSize(StackArray* stack)
{
return stack->top;
}
bool SA_IsEmpty(StackArray* stack)
{
return stack->top == 0;
}
bool SA_IsFull(StackArray* stack)
{
return stack->top == stack->capacity;
}
main.cpp
#include "StackArray.h"
using namespace std;
int main()
{
StackArray* stack;
SA_CreateStack(&stack, 10);
SA_Push(stack, 3);
SA_Push(stack, 37);
SA_Push(stack, 11);
SA_Push(stack, 12);
cout << "capacity : " << stack->capacity << " , Size : "
<< SA_GetSize(stack) << " , top : " << SA_Top(stack);
int debug = -1;
}링크드 리스트로 스택 구현하기
링크드 리스트로 스택을 구현하면 장점이 뭘까? 용량의 제한이 없다는 것이다. 링크드 리스트를 활용한 노드는 다음과 같다.
struct Node
{
char* data;
Node* nextNode;
};
struct LinkedListStack
{
Node* list; // 노드의 헤드.
Node* top; // 노드의 테일.
};노드의 테일을 만들지 않아도 접근 가능하다. 하지만 링크드 리스트의 단점인, 시간이 많이 걸린다. 포인터 하나로 이 단점을 없앨 수 있다
다음은 나머지 함수들이다. 시간은 좀 걸렸지만 그렇게 어려운 건 없다.
void LLS_CreateStack(LinkedListStack** stack)
{
(*stack) = new LinkedListStack;
(*stack)->list = nullptr;
(*stack)->top = nullptr;
}
void LLS_DestroyStack(LinkedListStack* stack)
{
if (LLS_IsEmpty(stack))
return;
while (!LLS_IsEmpty(stack))
{
Node* popNode = LLS_Pop(stack);
LLS_DestroyNode(popNode);
}
delete stack;
}
Node* LLS_CreateNode(const char* newData)
{
Node* newNode = new Node;
newNode->data = new char[strlen(newData) + 1];
strcpy_s(newNode->data, strlen(newData) + 1, newData);
newNode->next = nullptr;
return newNode;
}
void LLS_DestroyNode(Node* node)
{
delete[] node->data;
delete node;
}
void LLS_Push(LinkedListStack* stack, Node* newNode)
{
if (stack->list == nullptr)
{
stack->list = newNode;
stack->top = newNode;
}
else
{
stack->top->next = newNode;
stack->top = newNode;
}
}
Node* LLS_Pop(LinkedListStack* stack)
{
if (stack->list == nullptr)
return nullptr;
Node* last = stack->top;
if (stack->list == stack->top)
{
stack->list = nullptr;
stack->top = nullptr;
}
else
{
Node* temp = stack->list;
while (temp->next)
{
if (temp->next == last)
break;
temp = temp->next;
}
stack->top = temp;
stack->top->next = nullptr;
}
return last;
}
Node* LLS_Top(LinkedListStack* stack)
{
return stack->top;
}
int LLS_GetSize(LinkedListStack* stack)
{
int count = 0;
Node* temp = stack->list;
while (temp != nullptr)
{
temp = temp->next;
count++;
}
return count;
}
bool LLS_IsEmpty(LinkedListStack* stack)
{
return stack->list == nullptr;
}검증 코드.
int main()
{
int i = 0;
int count = 0;
Node* popped;
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);
cout << "Size : " << count << " , Top : " << LLS_Top(stack)->data << endl;
for (i = 0; i < count; i++)
{
if (LLS_IsEmpty(stack))
break;
popped = LLS_Pop(stack);
cout << "popped : " << popped->data;
LLS_DestroyNode(popped);
if (!LLS_IsEmpty(stack))
cout << "Current Top : " << LLS_Top(stack)->data << endl;
else
cout << "stack is empty" << endl;
}
int debug = -1;
}사칙 연산 계산기
어렵다.
enum SYMBOL
{
LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS = ')',
PLUS = '+', MINUS = '-',
MULTIPLY = '*', DIVIDE = '/',
SPACE = ' ', OPERAND
};
char NUMBER[] = { '0','1','2','3','4','5','6','7','8','9','.' };
int IsNumber(char cipher)
{
int arrayLength = sizeof(NUMBER);
for (int i = 0; i < arrayLength; i++)
{
if (cipher == NUMBER[i])
return 1;
}
}
unsigned int GetNextToken(char* expression, char* token, int* type)
{
unsigned int i = 0;
for (i = 0; expression[i] != 0; 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;
default:
break;
}
return priority;
}
int IsPrior(char operatorInStack, char operatorInToken)
{
return (GetPriority(operatorInStack, 1) > GetPriority(operatorInToken, 0));
}
void GetPostfix(char* infixExpression, char* postfixExpression)
{
char token[32];
int type = -1;
unsigned int position = 0;
unsigned int length = strlen(infixExpression);
LinkedListStack* stack;
LLS_CreateStack(&stack);
while (position < length)
{
position += GetNextToken(&infixExpression[position], token, &type);
if (type == OPERAND)
{
const char* tokenTemp = token;
strcat_s(postfixExpression, strlen(postfixExpression) + strlen(tokenTemp) + 1, tokenTemp);
strcat_s(postfixExpression, strlen(postfixExpression) + 2, " ");
}
else if (type == RIGHT_PARENTHESIS)
{
while (!LLS_IsEmpty(stack))
{
Node* popped = LLS_Pop(stack);
if (popped->data[0] == LEFT_PARENTHESIS)
{
LLS_DestroyNode(popped);
break;
}
else
{
strcat_s(postfixExpression, strlen(postfixExpression) + strlen(popped->data) + 1, popped->data);
LLS_DestroyNode(popped);
}
}
}
else
{
while (!LLS_IsEmpty(stack) && !IsPrior(LLS_Top(stack)->data[0], token[0]))
{
Node* popped = LLS_Pop(stack);
if (popped->data[0] != LEFT_PARENTHESIS)
strcat_s(postfixExpression, strlen(postfixExpression) + strlen(popped->data) + 1, popped->data);
LLS_DestroyNode(popped);
}
LLS_Push(stack, LLS_CreateNode(token));
}
}
while (!LLS_IsEmpty(stack))
{
Node* popped = LLS_Pop(stack);
if (popped->data[0] != LEFT_PARENTHESIS)
strcat_s(postfixExpression, strlen(postfixExpression) + strlen(popped->data) + 1, popped->data);
LLS_DestroyNode(popped);
}
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_s(resultString, tempResult, 10);
LLS_Push(stack, LLS_CreateNode(resultString));
}
}
resultNode = LLS_Pop(stack);
result = atof(resultNode->data);
LLS_DestroyNode(resultNode);
LLS_DestroyStack(stack);
return result;
}
Question, Think, Select