stack을 구현해 보자

스.택.을.구.현.해.보.자
알지? 연결리스트로할꺼임ㅋ 코드부터 보자

그리고 당연한 이야기겠지만 마지막에는 문제를 통해서 아래 코드를 검증해 볼 것이다.

struct node
{
	int num;
	struct node * pre;
};
struct node *f, *r;
void push(int);
struct node pop();
int isempty();
void push(int num)
{
	struct node *temp;
	temp = (struct node *)malloc(sizeof(struct node));
	temp->num = num;
	temp->pre = 0;
	if (!f && !r) // stack is empty
	{
		f = r = temp;
		return;
	}
	temp->pre = r;
	r = temp;
}
struct node pop()
{
	struct node *temp, ret;
	ret = *r;
	if (f == r) // stack size is one
	{
		free(f);
		f = r = 0;
	}
	else
	{
		temp = r;
		r = r->pre;
		free(temp);
	}
	return ret;
}
int isempty()
{
	return !f && !r;
}

이전 큐글과 마찬가지고 그림을 통해서 보자

f와 r을 전역변수로 저장했으니 모두 0(NULL)이 들어가 있다. 여기서 push를 해보자!



나는 큐와 스택을 구현 할 때에는 더미 노드를 안두기에 스택이 비어있을 때와 비어있지 않을때 가 조금 다르다(코드를 보면 if문이 있다.)

그러면 이제 스택이 비어 있지 않은 상황에서 다시 한번 push를 해보자!




이제 그림을 보면 알겠지만 f는 가장 나중에 들어온 곳을 가르키고 r은 가장 최근에 push된 곳을 가르킨다.

이제 pop을 해보자!! pop코드에는 stack size가 1일 때와 2이상일때로 나누어져 있다. 지금 상태는 2이상인 상태임을 잊지말자.




자 이제 보면 알겠지만 맨처음 상태에서 push를 한번 한 결과랑 같은 상태이다.
이제 이 상태(stack size is one)에서 pop을 다시한번 해보자!



자 여기까지 우리는 stack의 push, pop을 모두 살펴 봤다.

그러면 눈치챈 사람도 있을것이다. f와 r이 모두 0(NULL)이면 stack이 비어 있는 것이다!
그래서 따로 isempty()함수를 만들었다.

다음 글은 아마 dequeue가 될 것이다.

라고 했지만 witch가 쓴 이중연결리스트 글을보니 그 코드를 dequeue로 사용해도 될만한 코드이다. 그러니 다음 글은 hash table이 될 예정이다.

출처 : https://www.acmicpc.net/problem/10828

#include<stdio.h>
#include<malloc.h>
struct node
{
	int num;
	struct node *pre, *next;
};
struct node *f, *r;
int size;
void push(int);
struct node pop();
int isempty();
struct node top();
void make_answer();
int main(void)
{
	make_answer();
	return 0;
}
void make_answer()
{
	int n, num;
	char line[10];
	struct node pnode;
	size = 0;
	f = r = 0;
	scanf("%d", &n);
	while (n--)
	{
		scanf("%s", line);
		if (line[1] == 'u')
		{
			scanf("%d", &num);
			push(num);
		}
		else if (line[0] == 'p' && line[1] == 'o')
		{
			if (isempty())
			{
				printf("-1\n");
			}
			else
			{
				pnode = pop();
				printf("%d\n", pnode.num);
			}
		}
		else if (line[1] == 'i')
		{
			printf("%d\n", size);
		}
		else if (line[1] == 'm')
		{
			printf("%d\n", isempty());
		}
		else if (line[0] == 't' && line[1] == 'o')
		{
			if (isempty())
			{
				printf("-1\n");
			}
			else
			{
				pnode = top();
				printf("%d\n", pnode.num);
			}
		}
	}
	while (!(isempty()))
	{
		pop();
	}
}
void push(int num)
{
	struct node * temp;
	size++;
	temp = (struct node *)malloc(sizeof(struct node));
	temp->next = temp->pre = 0;
	temp->num = num;
	if (f == 0 && r == 0)
	{
		f = r = temp;
		return;
	}
	else
	{
		temp->next = f;
		f->pre = temp;
		f = temp;
		return;
	}
}
struct node pop()
{
	struct node *temp, result;
	size--;
	result = *f;
	temp = f;
	if (f == r)
	{
		free(temp);
		f = r = 0;
	}
	else
	{
		f = f->next;
		f->pre = 0;
		free(temp);
	}
	return result;
}
int isempty()
{
	if (!size)
	{
		return 1;
	}
	return 0;
}
struct node top()
{
	struct node result;
	result = *f;
	return result;
}

Q. isemty()가 다른데요??
A. 갯수로 판별해도 된다................

Q. stack을 사용하는 다른 문제는요?
A. 미안... 내가 생각해 봤는데 stack쓴 기억 별로 없어... 그래도 준비해봄
https://www.acmicpc.net/problem/17298
https://www.acmicpc.net/problem/17162