[Data Struct] 스택 (Stack) - 링크드 리스트를 이용한 스택

스택은 쌓다의 의미

모든 스택의 공통점

LIFO 형식 (Last in First out)
Pop() - 스택에서 꺼내는 함수
Push() - 스택에 넣는 함수

링크드 리스트를 사용 할 수 있고 배열을 사용 할 수도 있다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _NODE {
	int Data;
	struct _NODE *Next;
} NODE;

NODE *head, *end;
NODE *ptrNode;

void InitializeStack(void);
void Push(int);
void DisplayStack(void);
int Pop(void);

int main()
{
	int ret;
	InitializeStack();

	Push(1);
	Push(3);
	Push(10);
	Push(20);
	Push(12);

	printf("다섯 번의 Push() 함수의 호출 후 실행 결과\n");
	DisplayStack();

	ret=Pop();
	ret=Pop();
	ret=Pop();

	printf("\n세 번의 Pop() 함수의 호출 후 실행 결과 \n");
	DisplayStack();
	return 0;
}

/* 스택 초기화 함수 */
void InitializeStack(void)
{
	head = (NODE *)malloc(sizeof(NODE));
	end = (NODE *)malloc(sizeof(NODE));

	head -> Next=end;
	end -> Next=end;
}

void Push(int num)
{
	ptrNode = (NODE *)malloc(sizeof(NODE));
	ptrNode->Data = num;
	ptrNode->Next=head->Next;
	head->Next = ptrNode;
}

int Pop(void)
{
	int ret;

	ptrNode = head ->Next;
	head ->Next = head ->Next ->Next;
	ret=ptrNode ->Data;

	free(ptrNode);

	return ret;
}

void DisplayStack(void)
{
	NODE *indexNode;
	printf("head -> ");
	for(indexNode=head->Next; indexNode !=end; indexNode = indexNode ->Next)
	printf("%d -> ", indexNode ->Data);
	printf("end");

}

스택 계산기( 가로 포함 계산)

#include <stdio.h>
#include <string.h>

#define MAX 100
#define TURE 1
#define FALSE 0

/* Definition of Global Variables */
char OperatorStack[100];
char OperandStack[100];
int OperatorTop;
int OperandTop;

/* Definition of Blobal Functions */

void InitializeStack(void);
void OperatorPush(char); // 연산자
void OperandPush(int);
char OperatorPop(void); // 피연산자
int OperandPop(void);
int IsEmptyOperatorStack(void);
int IsEmptyOperandStack(void);

int GreaterOpr(char, char);
int Calculate(int, int, char);

void main(void)
{
	char buf[80];
	int len, i;
	int opn1, opn2; // 피연산자 1, 2
	char opr, c;
	char tmpopr;
	InitializeStack();

	strcpy(buf, "1 + 2 * (1 + 3)");

	len = strlen(buf);
	i=0;
	while(i<len)
	{
		c=buf[i++];

		if(c == ' ')
		continue;
		else if(c<='9' && c>='0')
		OperandPush(c-'0'); // c-'0'을 해줘야 하는 이유는 c가 캐릭터형이기 때문이다.
		// 따라서 '0'을 빼줘야 int 형처럼 숫자를 같는다. 아스키코드표 참고
		else if(c=='+' || c=='-' || c=='*' || c== '/')
		{
			if(IsEmptyOperatorStack())
			OperatorPush(c);
			else
			{
				opr=OperatorPop();
				if(GreaterOpr(opr, c)) // 스택에 저장된 값과 현재 저장할 스택의 값(연산자)을 비교한다.
				{
					opn2=OperandPop(); // 피연산자에 저장되는 스택에서 차례로 2개를 꺼낸다.
					opn1=OperandPop();
					opn1=Calculate(opn1, opn2, opr); // 계산 함수에 넣는다.
					OperandPush(opn1); // 계산 값을 다시 넣는다.
					OperatorPush(c); // 계산 하지 않은 현재의 연산자를 스택에 넣는다.
				}
				else
				{
					OperatorPush(opr);
					OperatorPush(c);
				}
			}
		}
		else if(c=='(')
		{
			OperatorPush(c);
		}
		else if(c==')')
		{
			do
			{
				tmpopr=OperatorPop();
				if(tmpopr != '(')
				{
					opn2=OperandPop();
					opn1=OperandPop();
					opn1=Calculate(opn1, opn2, tmpopr);
					OperandPush(opn1);
				}
			}
			while(tmpopr !='(');
		}

	}
	while(!IsEmptyOperatorStack()){ // 계산되지 않고 저장된 나머지 스택을 꺼내 계산한다.
		opn1=OperandPop();
		opn2=OperandPop();
		opr=OperatorPop();
		opn1=Calculate(opn1, opn2, opr);
		OperandPush(opn1);
	}

	printf("%s = %d\n", buf, OperandPop());
}

void InitializeStack(void)
{
	OperatorTop = 0; // 0으로 초기화
	OperandTop = 0;
}

void OperatorPush(char opr)
{
	OperatorStack[OperatorTop++] = opr;
}

void OperandPush(int opn)
{
	OperandStack[OperandTop++] = opn;
}

char OperatorPop(void)
{
	return OperatorStack[--OperatorTop];
}

int OperandPop(void)
{
	return OperandStack[--OperandTop];
}

int IsEmptyOperandStack(void)
{
	if(OperandTop == 0)
	return TURE;
	else
	return FALSE;
}

int IsEmptyOperatorStack(void)
{
	if(OperatorTop==0) // InitializeStack에 의해 초기화된 값이 0이면 스택에 아무것도 없다는 뜻이다.
	return TURE;
	else
	return FALSE;
}

int GreaterOpr(char opr1, char opr2)
{
	if(opr1=='*' || opr1 == '/')
	{
		if(opr2=='+' || opr2=='-')
		return TURE;
		else
		return FALSE;
	}
	else /*opr1 =='+' || opr1=='-' */
	return FALSE;
}

int Calculate(int opn1, int opn2, char opr)
{
	switch(opr)
	{
	case '+':
		opn1=opn1+opn2;
		break;
	case '-':
		opn1=opn2-opn1;
		break;
	case '*':
		opn1=opn1*opn2;
		break;
	case '/':
		opn1=opn2/opn1;
		break;
	}
	return opn1;
}

스택 계산기

#include <stdio.h>
#include <string.h>

#define MAX 100
#define TURE 1
#define FALSE 0

/* Definition of Global Variables */
char OperatorStack[100];
char OperandStack[100];
int OperatorTop;
int OperandTop;

/* Definition of Blobal Functions */

void InitializeStack(void);
void OperatorPush(char); // 연산자
void OperandPush(int);
char OperatorPop(void); // 피연산자
int OperandPop(void);
int IsEmptyOperatorStack(void);
int IsEmptyOperandStack(void);

int GreaterOpr(char, char);
int Calculate(int, int, char);

void main(void)
{
	char buf[80];
	int len, i;
	int opn1, opn2; // 피연산자 1, 2
	char opr, c;
	InitializeStack();

	strcpy(buf, "1 + 2 * 3 - 1");

	len = strlen(buf);
	i=0;
	while(i<len)
	{
		c=buf[i++];

		if(c == ' ')
		continue;
		else if(c<='9' && c>='0')
		OperandPush(c-'0'); // c-'0'을 해줘야 하는 이유는 c가 캐릭터형이기 때문이다.
		// 따라서 '0'을 빼줘야 int 형처럼 숫자를 같는다. 아스키코드표 참고
		else if(c=='+' || c=='-' || c=='*' || c== '/')
		{
			if(IsEmptyOperatorStack())
			OperatorPush(c);
			else
			{
				opr=OperatorPop();
				if(GreaterOpr(opr, c)) // 스택에 저장된 값과 현재 저장할 스택의 값(연산자)을 비교한다.
				{
					opn2=OperandPop(); // 피연산자에 저장되는 스택에서 차례로 2개를 꺼낸다.
					opn1=OperandPop();
					opn1=Calculate(opn1, opn2, opr); // 계산 함수에 넣는다.
					OperandPush(opn1); // 계산 값을 다시 넣는다.
					OperatorPush(c); // 계산 하지 않은 현재의 연산자를 스택에 넣는다.
				}
				else
				{
					OperatorPush(opr);
					OperatorPush(c);
				}
			}
		}
	}
	while(!IsEmptyOperatorStack()){ // 계산되지 않고 저장된 나머지 스택을 꺼내 계산한다.
		opn1=OperandPop();
		opn2=OperandPop();
		opr=OperatorPop();
		opn1=Calculate(opn1, opn2, opr);
		OperandPush(opn1);
	}

	printf("%s = %d\n", buf, OperandPop());
}

void InitializeStack(void)
{
	OperatorTop = 0; // 0으로 초기화
	OperandTop = 0;
}

void OperatorPush(char opr)
{
	OperatorStack[OperatorTop++] = opr;
}

void OperandPush(int opn)
{
	OperandStack[OperandTop++] = opn;
}

char OperatorPop(void)
{
	return OperatorStack[--OperatorTop];
}

int OperandPop(void)
{
	return OperandStack[--OperandTop];
}

int IsEmptyOperandStack(void)
{
	if(OperandTop == 0)
	return TURE;
	else
	return FALSE;
}

int IsEmptyOperatorStack(void)
{
	if(OperatorTop==0) // InitializeStack에 의해 초기화된 값이 0이면 스택에 아무것도 없다는 뜻이다.
	return TURE;
	else
	return FALSE;
}

int GreaterOpr(char opr1, char opr2)
{
	if(opr1=='*' || opr1 == '/')
	{
		if(opr2=='+' || opr2=='-')
		return TURE;
		else
		return FALSE;
	}
	else /*opr1 =='+' || opr1=='-' */
	return FALSE;
}

int Calculate(int opn1, int opn2, char opr)
{
	switch(opr)
	{
	case '+':
		opn1=opn1+opn2;
		break;
	case '-':
		opn1=opn2-opn1;
		break;
	case '*':
		opn1=opn1*opn2;
		break;
	case '/':
		opn1=opn2/opn1;
		break;
	}
	return opn1;
}