[알고리즘-백준 10828번] 스택 (C언어)

• 스택(stack)
  • 스택(stack) = 쌓다   -> 데이트러르 차곡차곡 쌓아 올린 형태의 자료구조
  • 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조
  • top을 통해서 삭제, 삽입 가능 = 후입선출 (LIFO = Last In First Out)
• 스택 구현
  • 배열 기반으로 구현
  • 동적배열 기반으로 구현
  • 연결 리스트로 구현

---

배열 기반으로 구현

//배열 기반으로 stack 구현
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
typedef struct ArrayStack {
	int top;
	int capacity;
	int* array;
}Stack;

//주어진 capacity 크기로 stack을 생성하는 함수
Stack* createStack(int capacity)
{
	Stack* stack = (Stack*)malloc(sizeof(Stack));
	if (!stack)
		return NULL;
	stack->capacity = capacity;
	stack->top = -1;
	stack->array = (int*)malloc(stack->capacity * sizeof(int));
	return stack;
}

//스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack)
{
	return (stack->top == -1);
}

//스택이 가득찼는지 확인하는 함수
int isFull(Stack* stack)
{
	return (stack->top == stack->capacity - 1);
}

//top 위치에 있는 값을 가져오는 함수
int peek(Stack* stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top];
}

//스택에 값을 추가하는 함수
void push(Stack* stack, int data)
{
	if (isFull(stack))
		printf("Stack is full\n");
	else {
		//top을 1 증가시키고 값을 top에 저장함
		stack->array[++stack->top] = data;
		printf("%d pushed to stack\n", data);
	}
}

//스택에 값을 삭제하는 함수
int pop(Stack* stack)
{
	if (isEmpty(stack))
	{
		printf("Stack is empty\n");
		return INT_MIN;
	}
	else
		return (stack->array[stack->top--]);
}

void main() {
	Stack* stack = createStack(3);

	push(stack,1);
	push(stack, 2);
	push(stack, 3);
	push(stack, 4);
	printf("%d popped from stack\n", pop(stack));

	
}

결과

 

주의할점

• <stdlib.h>는 malloc를 쓰려면 써야하는 헤더파일이다.
• typedef 키워드는 이미 존재하는 구조체에 새로운 이름을 붙일 때 사용한다.

문제점

• 스택의 사이즈가 정적이기 때문에 꽉 찬 스택에 push 할 수 없는 문제점이 있다.

 

---

동적 배열을 기반으로 구현

"배열 기반으로 구현"에서 push 함수 수정.

//동적 배열을 기반으로 stack 구현
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
typedef struct ArrayStack {
	int top;
	int capacity;
	int* array;
}Stack;

//주어진 capacity 크기로 stack을 생성하는 함수
Stack* createStack(int capacity)
{
	Stack* stack = (Stack*)malloc(sizeof(Stack));
	if (!stack)
		return NULL;
	stack->capacity = capacity;
	stack->top = -1;
	stack->array = (int*)malloc(stack->capacity * sizeof(int));
	return stack;
}

//스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack)
{
	return (stack->top == -1);
}

//스택이 가득찼는지 확인하는 함수
int isFull(Stack* stack)
{
	return (stack->top == stack->capacity - 1);
}

//top위치에 있는 값을 가져오는 함수
int peek(Stack* stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top];
}

//스택에 값을 추가하는 함수
void push(Stack* stack, int data)
{
	if (isFull(stack)) {
		stack->capacity *= 2*sizeof(stack);
		realloc(stack, stack->capacity);
	}
	
	stack->array[++stack->top] = data;
	printf("%d pushed to stack\n", data);
}

//스택에 값을 삭제하는 함수
int pop(Stack* stack)
{
	if (isEmpty(stack))
	{
		printf("Stack is empty\n");
		return INT_MIN;

	}
	else
		return (stack->array[stack->top--]);
}

void main() {
	Stack* stack = createStack(3);

	push(stack, 1);
	push(stack, 2);
	push(stack, 3);
	push(stack, 4);
	printf("%d popped from stack\n", pop(stack));


}

결과

주의할 점

• realloc(stack-Stack*자료형, capacity-사이즈 재할당 capacity) 사용후, 이전까지 넣었던 값들은 그대로 있다. 동적배열의 크기인 capacity만 늘려준 것이기 때문이다.

 

---

연결 리스트로 구현

연결리스트로 스택을 구현하면, 리스트 앞에 노드를 추가하거나 삭제하면 되기 때문에 자유롭게 사이즈를 증가시킬 수 있다.

push : 리스트 맨 앞에 새로운 노드를 추가하도록 구현

pop : 리스트 맨 앞 노드를 삭제하도록 구현

//연결리스트로 스택 구현
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct ListStack
{
	int data;
	struct ListStack* next;

}Stack;

int isEmptyStack(Stack* Top)
{
	return (Top == NULL);
}

void push(Stack** Top, int data)
{
	Stack* newNode = NULL;
	newNode = (Stack*)malloc(sizeof(Stack));
	if (newNode == NULL)
	{
		printf("Stack is full\n");
		return;
	}
	//리스트 맨 앞에 새로운 노드를 추가합니다.
	newNode->data = data;
	newNode->next = *Top;
	*Top = newNode;
	printf("%d pushed\n", newNode->data);
}

int pop(Stack** Top)
{
	Stack* temp = NULL;
	int data = 0;
	if (isEmptyStack(*Top))
	{
		printf("Stack is Empty\n");
		return INT_MIN;
	}
	else
	{
		//Top위치 (리스트 맨 앞)에 있는 노드를 제거합니다
		temp = *Top;
		*Top = temp->next;
		data = temp->data;
		free(temp);
	}
	return data;
}

void main(void)
{
	Stack* S = NULL;
	push(&S, 1);
	push(&S, 3);
	push(&S, 5);
	printf("%d poped from stack\n", pop(&S));
	
}

결과