[C언어] Stack (스택)

자료구조와 알고리즘/자료구조

[C언어] Stack (스택)

jaewpark 2021. 9. 2. 10:47

FILO(Last-In-First-Out), 후입선출의 특성

구현해야 하는 필수 요소

푸시 연산
- ⚠️ 스택의 크기를 초과해 새로운 자료를 추가하지 못하는 현상을 오버플로
- 스택에 새로운 자료를 추가

팝 연산
- ⚠️ 아무 자료가 없는 빈 스택에 연산을 하게 되면 언더플로 현상 발생
- 스택에서 자료를 제거

피크
- 연산자료를 제거 🚫
- 스택의 맨 위 자료를 반환

특정 정보 기억 후 재이용 할 때 주로 사용

컴퓨터 알고리즘에서 자주 쓰이는 데이터구조
수행 중의 프로그램 함수나 서브프로그램들의 복귀주소와 관련된 여러 정보들을 저장

🐬배열리스트를 이용한 구현

#include "array_list.h"

int	ft_push(t_array_list *list, int *top, int new_data)
{
	t_array_node new_node;

	if (list->curr_element_cnt == list->max_element_cnt)
	{
    printf("Error! Overflow\n");
    return (-1);
  }
	new_node.data = new_data;
	list->p_element[(*top) + 1] = new_node;
	++(*top);
	++list->curr_element_cnt;
	return (0);
}

int	ft_pop(t_array_list *list, int *top)
{
	if (list->curr_element_cnt == 0)
  {
    printf("Error! Underflow\n");
		return (-1);
  }
	list->p_element[*top].data = 0;
	--list->curr_element_cnt;
	--(*top);
	return (0);
}

int ft_peek(t_array_list *list, int *top)
{
	if (list->curr_element_cnt == 0)
		return (-1);
	return (list->p_element[*top].data);
}

#include "array_list.h"

int ft_get_array_list_length(t_array_list *p_list)
{
	int cnt = 0;
	for(int i = 0; i < p_list->max_element_cnt; i++)
	{
		if (p_list->p_element[i].data != 0)
			++cnt;
	}
	return (cnt);
}

int ft_is_array_list_full(t_array_list *p_list)
{
	int i = -1;
	int cnt = -1;
	if (p_list->p_element == NULL)
		return (1);
	while (++i < p_list->max_element_cnt)
	{
		if (p_list->p_element[i].data == 0)
			++cnt;
	}
	return (cnt);
}

int ft_add_element_to_array_list(t_array_list *p_list, int position, t_array_node element)//뒤쪽이 빈 거라고 가정
{
	if (ft_is_array_list_full(p_list) < 0)
		return (-1);
	int i = p_list->max_element_cnt - 1;
	while (i > position)
	{
		p_list->p_element[i].data = p_list->p_element[i - 1].data;
		--i;
	}
	p_list->p_element[i].data = element.data;
	++p_list->curr_element_cnt;
	return (0);
}  

int ft_remove_element_from_array_list(t_array_list *p_list, int position)
{
	int i = position;
	while (i < p_list->max_element_cnt - 1)
	{	
		p_list->p_element[i].data = p_list->p_element[i + 1].data;
		++i;
	}
	p_list->p_element[i].data = 0;
	--p_list->curr_element_cnt;
	return (0);
}

void ft_delete_array_list(t_array_list *p_list)
{
	for(int i = 0; i < p_list->max_element_cnt; i++) //배열 원소 삭제
		p_list->p_element[i].data = 0; //이게 다일까?
	free(p_list->p_element);
	p_list->p_element = NULL;
	p_list->max_element_cnt = 0;
	p_list->curr_element_cnt = 0;
	return ;
}

void ft_display_array_list(t_array_list *p_list)
{
	if (p_list->p_element == NULL)
		return ;
	for (int i = 0; i < p_list->max_element_cnt; i++)
		printf("array[%d]: %d\n", i, p_list->p_element[i].data);
	return ;
}

void ft_clear_array_list(t_array_list *p_list)
{
	for(int i = 0; i < p_list->max_element_cnt; i++) //배열 원소 삭제
		p_list->p_element[i].data = 0; //이게 다일까?
	p_list->curr_element_cnt = 0;
	return ;
}

t_array_node *ft_get_element_from_array_list(t_array_list *p_list, int position)
{
	return (&(p_list->p_element[position]));
}

t_array_list *ft_create_array_list(int max_element_cnt)
{
	t_array_list *array_list;

	array_list = (t_array_list *)malloc(sizeof(t_array_list));
	array_list->max_element_cnt = max_element_cnt;
	array_list->curr_element_cnt = 0;
	array_list->p_element = (t_array_node *)malloc(sizeof(t_array_node) * max_element_cnt);
	for(int i = 0; i < max_element_cnt; i++) //배열 초기화
		array_list->p_element[i].data = 0;
	return (array_list);
}

🐬링크드 리스트를 이용한 구현

#include "linked_list.h"

void ft_push(t_linked_list *pList, int data){
  t_linked_list_node *new_node = NULL;
  new_node = ft_create_element(data);
  if (!new_node)
  {
    printf("Error! Wrong malloc\n");
    return ;
  }
  if (pList->header_node->next == NULL)
    pList->header_node->next = new_node;
  else
  {
    new_node->next = pList->header_node->next;
    pList->header_node->next = new_node;
  }
}

void ft_pop(t_linked_list *pList){
  t_linked_list_node *tmp_node = NULL;
  if (pList->header_node->next == NULL)
  {
    printf("Error! Underflow\n");
    return ;
  }
  tmp_node = pList->header_node->next;
  pList->header_node->next = pList->header_node->next->next;
  tmp_node->next = NULL;
  free(tmp_node);
}

int ft_peek(t_linked_list *pList){
  return (pList->header_node->next->data);
}

#include "linked_list.h"

void	ft_reverse_linked_list(t_linked_list *p_list)
{
	t_linked_list_node 		*origin;
	t_linked_list_node		*curr;

	if (p_list->num_of_current_element <= 1)
		return ;
	curr = p_list->header_node->next; 
	origin = curr->next;
	curr->next = NULL; 
	while (origin != NULL)
	{
		curr = origin;
		origin = origin->next;
		curr->next = p_list->header_node->next;
		p_list->header_node->next = curr;
	}
	return ;
}

t_linked_list	*ft_create_linked_list()
{
	t_linked_list	*list;

	list = (t_linked_list *)malloc(sizeof(t_linked_list));
	if (list == NULL)
		return (NULL);
	list->header_node = ft_create_element(0);
	list->num_of_current_element = 0;
	return (list);
}

int	ft_add_element_to_linked_list(t_linked_list *p_list, int position, t_linked_list_node *element)
{
	t_linked_list_node *curr;

	curr = p_list->header_node;
	int cnt = 0;
	while (curr)
	{
		if (cnt == position)
		{
			element->next = curr->next;
			curr->next = element;
			++p_list->num_of_current_element;
			return (0);
		}
		++cnt;
		curr = curr->next;
	}
	return (0);
}

int	ft_add_last_element_to_linked_list(t_linked_list *p_list, t_linked_list_node *element)
{
	t_linked_list_node *curr;

  	if (p_list->header_node->next == NULL)
  	{  
   		p_list->header_node->next = element;
   		++p_list->num_of_current_element;
    return (0);
  	}
  	curr = p_list->header_node->next;
	while (curr->next != NULL)
	{
		curr = curr->next;
	}
  	++p_list->num_of_current_element;
	curr->next = element;
	return (0);
}

void	ft_print_linked_list(t_linked_list *p_list)
{
	t_linked_list_node *curr;
	
	curr = p_list->header_node->next;
	int i = 0;
	while (curr)
	{
		printf("node[%d] -> data: %d\n", i, curr->data);
		++i;
		curr = curr->next;
	}
	return ;
}

t_linked_list_node	*ft_create_element(int data)
{
	t_linked_list_node *new_element;
	
	new_element = (t_linked_list_node *)malloc(sizeof(t_linked_list_node));
	if (new_element == NULL)
		return (NULL);
	new_element->data = data;
	new_element->next = NULL;
	return (new_element);
}

int	ft_remove_element_from_linked_list(t_linked_list *p_list, int position)
{
	int					idx;
	t_linked_list_node	*curr;
	t_linked_list_node	*tmp;

	if (position >= p_list->num_of_current_element)
		return (-1);
	idx = 0;
	curr = p_list->header_node;
	while (curr)
	{
		if (idx == position)
		{
			tmp = curr->next;
			curr->next = curr->next->next;
			free(tmp);
			--p_list->num_of_current_element;
			return (0);
		}
		++idx;
		curr = curr->next;
	}
	return (0);
}

t_linked_list_node	*ft_get_element_from__linked_list(t_linked_list *p_list, int position)
{
	int					idx;
	t_linked_list_node	*curr;

	idx = 0;
	curr = p_list->header_node->next;
	while (curr)
	{
		if (idx == position)
		{
			return (curr);
		}
		++idx;
		curr = curr->next;
	}
	return (NULL);
}

void	ft_clear_linked_list(t_linked_list *p_list)
{
	t_linked_list_node	*curr;
	
	curr = p_list->header_node->next;
	while (curr)
	{
		curr->data = 0;
		curr = curr->next;
	}
	p_list->num_of_current_element = 0;
	return ;
}

void	ft_delete_linked_list(t_linked_list *p_list)
{
	t_linked_list_node *curr;
	t_linked_list_node *tmp;

	curr = p_list->header_node;
	tmp = curr;
	while (curr)
	{
		curr = curr->next;
		free(tmp);
		tmp = curr;
	}
	p_list->header_node->next = NULL;
	p_list->num_of_current_element = 0;
	return ;
}

미로찾기 구현

💨 data를 담는 것을 구조체에 만들어서 저장

#ifndef PROJECT_H
# define PROJECT_H

# define  UP    0
# define  RIGHT 1
# define  DOWN  2
# define  LEFT  3

# define  MAPSIZE 7

int DIRECTION_OFFSETS[4][2] = {
    {0, -1}, // 위쪽으로이동.
    {1, 0}, // 오른쪽으로이동.
    {0, 1}, // 아래쪽으로이동.
    {-1, 0} // 왼쪽으로이동.
  };

void  move(t_coordinate *point, int direction);
int   isMovable(int map[][MAPSIZE], int x, int y);
void  findRoute(int map[][MAPSIZE]);

#endif

#include "linked_list.h"
#include "project.h"

int main () {
  
  int myMaze[MAPSIZE][MAPSIZE] = {
    {0, 0, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1},
    {1, 1, 1, 0, 1, 1, 1},
    {1, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0},
  };

  findRoute(myMaze);

  return (0);
}

void move(t_coordinate *point, int direction)
{
  point->x += DIRECTION_OFFSETS[direction][0];
  point->y += DIRECTION_OFFSETS[direction][1];
}

/*
  인자로 넘겨진 위치가 이동가능한지? -> 맵크기비교 + 그 자리가 0인지?
*/
int isMovable(int map[][MAPSIZE], int x, int y)
{
  if (x < 0 || x > MAPSIZE - 1 || y < 0 || y > MAPSIZE - 1)
    return (0);
  if (map[y][x] == 1)
    return (0);
  return (1);
}

void  findRoute(int map[][MAPSIZE])
{
  t_coordinate  point;
  t_linked_list *list;

  list = ft_create_linked_list();
  point.x = 0;
  point.y = 0;

  while (!(point.x == MAPSIZE - 1 && point.y == MAPSIZE - 1)) {  
    map[point.y][point.x] = 1;
    //printf("[%d, %d]\n", point.x, point.y);
    if (isMovable(map, point.x, point.y - 1)) {
      ft_push(list, point);
      move(&point, UP);
      //printf("u");
    }
    else if (isMovable(map, point.x + 1, point.y)) {
      ft_push(list, point);
      move(&point, RIGHT);
      //printf("r");
    }
    else if (isMovable(map, point.x, point.y + 1)) {
      ft_push(list, point);
      move(&point, DOWN);
      //printf("d");
    }
    else if (isMovable(map, point.x - 1, point.y)) {
      ft_push(list, point);
      move(&point, LEFT);
      //printf("l");
    }
    else {  // 전부 못간다면
      if (point.x == 0 && point.y == 0) // 출구 없음!
      {
        printf("Error! No EXIT");
        exit(1);
      }
      point = ft_peek(list)->point; // 이전 위치로 이동
      ft_pop(list);
      //printf("what?\n");
    }
  }
  if (point.x == MAPSIZE - 1 && point.y == MAPSIZE - 1)
    ft_push(list, point);
  ft_reverse_linked_list(list); // 역순
  ft_print_linked_list(list); //출력
}