스택 (Stack)

배열을 활용한 스택

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

#define MAX 1000
#define INF 99999

int stack[MAX];
int top = -1;
void Push(int data)
{
	if (top == MAX - 1)
	{
		printf("스택 오버 플로우 발생\n");
		return;
	}
	stack[++top] = data;
}

int Pop()
{
	if (top == -1)
	{
		printf("스택 언더 플로우 발생\n");
		return -INF;
	}
	return stack[top--];
}

void Show()
{
	
	for (int i=top; i > -1; i--)
	{
		printf("%d ", stack[i]);
	}
}

 

 

링크리스트를 활용한 스택

* 배열의 비해 장점은 공간활용도가 높다 (배열의 경우 초기에 크기를 선언해주어야 하기 때문에 메모리 공간 낭비가 많지만 링크리스트는 쓸만큼만 할당하기 때문에 메모리 활용에서 효율적이다)

#include <stdio.h>
#include <stdlib.h>
#define INF 999999
struct Node
{
	int data;
	Node *next;
};

struct Stack
{
	Node* top;
};


void Push(Stack *stack,int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	// 아무것도 없는 상태에서도 stack->top은 null 이기때문에
	node->next = stack->top;
	stack->top = node;
}

int Pop(Stack *stack)
{
	if (stack->top == NULL)
	{
		printf("언더 플로우 발생\n");
		return -INF;
	}
	Node *node = stack->top;
	int data = node->data;
	stack->top = node->next;
	free(node);
	return data;
}
void Show(Stack *stack)
{
	Node* node = stack->top;
	while (node != NULL)
	{
		printf("%d ", node->data);
		node = node->next;
	}
}
int main()
{
	Stack stack;
	stack.top = NULL;
	Push(&stack, 3);
	Push(&stack, 4);
	Push(&stack, 4);
	Push(&stack, 4);
	Push(&stack, 4);

	Push(&stack, 1);
	Pop(&stack);
	Pop(&stack);
	Pop(&stack);

	Show(&stack);
	return 0;
}