[23일차] 스택(Stack) & 큐(Queue) & 트리(Tree) & 재귀함수(Recursive func)

제목에서 느낄 수 있듯이 진도가 슉슉 나갔다.

 

[연결 리스트]

• 단일 연결 리스트 구현,
• 이중 연결리스트 구현,
• 더미 노드를 활용한 연결 리스트 구현,

[스택]

• 배열을 활용한 스택 구현,
• 연결 리스트를 활용한 스택 구현,

[큐]

• 원형 큐 구현,
• 배열을 통한 큐 구현,
• 연결 리스트를 활용한 큐 구현,

[트리]

• 트리 구현

[재귀 함수와 알고리즘]

• 재귀 함수 - 팩토리얼, 피보나치, 하노이의 탑 재귀 및 비 재귀로 구현하기.

---

대략 나간 내용은 다음과 같다.

각각의 구현마다 C를 활용한 코드 예제가 있었는데, 수업시간에는 모든 예제를 하지 않고 개념을 간단히 한 후, 몇 개의 예제만 한다.

그러다 보니 개념적으로는 머리에 그림이 그려져도 이를 C로 구현하기 위해 코드를 하나씩 이해해가느라 수업 진도에 따라가기가 벅차다.

남아서 자습을 하며 단일 연결 리스트부터 예제 코드를 뜯어보며 살펴보았다.

큐까지는 어느정도 코드를 다시 보면 이해할 만큼 이해가 되었지만, 트리는 아직 많이 미숙하다.

다행히 팩토리얼과 피보나치는 예전에 혼자서 많이 해본 것이기 때문에 어렵지 않았다.

 

 

 

- 다음 코드는 배열을 활용한 스택을 이용하여 중위-표기법을 후위-표기법으로 변환한 뒤, 이를 계산하는 코드이다.

postfix 함수를 통해 후위 표기법으로 변환하는 과정을 알 수 있고,

calc 함수를 통해 후위 표기법의 계산 과정을 알 수 있었다.

개인적으로 후위표기법으로 어떻게 연산이 되는 건지 궁금했는데, 함수를 뜯어보며 스택을 잘 활용하면 된다는 것을 알 수 있었다.

/*                                                           */
/*  CALC.C  :  Evaluate expression , command line version    */
/*                                                           */

//#include "uart.h"
//#include "clkcon.h"
#include <stdio.h>
#define MAX  100

int stack[MAX];
int top; 

void init_stack(void)
{
    top = -1;
}

int push(int t)
{
    if (top >= MAX - 1)
	{
        printf("    Stack overflow.\n");
       // exit(1);
	}
    stack[++top] = t;
    return t;
}

int pop(void)
{
    if (top < 0)
	{
        printf("    Stack underflow.\n");
       // exit(1);
	}
    return stack[top--];
}

int get_stack_top(void)
{
    return (top < 0) ? -1 : stack[top];
}

int is_stack_empty(void)
{
    return (top < 0);
}

int is_operator(int k)
{
    return (k == '+' || k == '-' || k == '*' || k == '/');
}

int is_legal(char *s)
{
    int f = 0;
    while (*s)
	{
		while (*s == ' ')   /* remove space */
			s++;
		if (is_operator(*s))
				f--;
		else
			{
			f++;
			while (*s != ' ')
			s++;
			}
		if (f < 1) break;
		s++;
	}
    return (f == 1);   /* legal if valuable - operator == 1 */
}

int precedence(int op)
{
    if (op == '(') return 0;
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    else return 3;
}

void postfix(char *dst, char *src)
{
    char c;
    init_stack();
    while (*src)
	{
		if (*src == '(')
		{
			push(*src);
			src++;
		}
		else if (*src == ')')
		{
			while (get_stack_top() != '(')
			{
				*dst++ = pop();
				*dst++ = ' ';
			}
			pop();
			src++;
		}
		else if (is_operator(*src))
		{
			while (!is_stack_empty() && precedence(get_stack_top()) >= precedence(*src))
			{
				*dst++ = pop();
				*dst++ = ' ';
			}
			push(*src);
			src++;
		}
		else if (*src >= '0' && *src <= '9')
		{
			do
			{
				*dst++ = *src++;
			} while (*src >= '0' && *src <= '9');
			*dst++ = ' ';
		}
		else
			src++;
	}
    while (!is_stack_empty())
	{
		*dst++ = pop();
		*dst++ = ' ';
	}
    dst--;
    *dst = 0;
}

int calc(char *p)
{
    int i;
    init_stack();
    while (*p)
	{
        if (*p >= '0' && *p <= '9')
		{
            i = 0;
            do
			{
                i = i * 10 + *p - '0';
                p++;
			} while (*p >= '0' && *p <= '9');
            push(i);
		}
        else if (*p == '+')
		{
            push(pop() + pop());
            p++;
		}
        else if (*p == '*')
		{
            push(pop() * pop());
            p++;
		}
        else if (*p == '-')
		{
            i = pop();
            push(pop() - i);
            p++;
		}
        else if (*p == '/')
		{
            i = pop();
            push(pop() / i);
            p++;
		}
        else
            p++;
	}
    return pop();
}

void main(void)
{
    int r;
    char exp[256];

    char argv[200];

    gets(argv);
    
    postfix(exp, argv);
    printf("Postfix : %s\n", exp);
    if (!is_legal(exp))
	{
		printf("Expression is not legal!\n");
	//	exit(1);
	}
		r = calc(exp);
		printf("Answer  : %d\n", r);
    }

 

- 연결리스트로 구현하는 스택

/*                                                           */
/*  STACK2.C  :  Stack using Linked list                     */
/*                                                           */

#include <stdlib.h>
#include "uart.h"
#include "clkcon.h"

typedef struct _node
{
    int key;
    struct _node *next;
} node;

node *head, *tail;

void init_stack(void)
{
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    tail->next = tail;
}

void clear_stack(void)
{
    node *t, *s;
    t = head->next;
    while (t != tail)
    {
        s = t;
        t = t->next;
        free(s);
    }
    head->next = tail;
}

int push(int data)
{
	node *t;
	t = (node*)malloc(sizeof(node));
	if(t==NULL)
	{
		Uart_Printf("Stack is overflow\n");
		return -1;
	}

	t->key = data;
	t->next = head->next;
	head->next = t;

	return data;
}

int pop(void)
{
	node *t;
	int i;
	if(head->next == tail)
	{
        	Uart_Printf("Stack is underflow\n");
	       return -1;
	}
	t = head->next;
	i = t->key;  
	head->next = t -> next;
	free(t);

	return i;
}


void ListStack_Main(void) 
{
	char value;
	
	init_stack();

	for(value = 'A'; value < 'E'; value++)
		push(value); 
	while(head->next != tail)
	{
		value = pop();
		Uart_Printf("%c\n", value);
	}
}

 

 

- 이후에도 배열을 활용한 큐의 구현

#include "uart.h"

#define SIZE 100

int queue[SIZE];

int front, rear;

void init_queue(void)
{
	front = rear = 0;
}

void queue_queue(void)
{
	front = rear = 0;
}

int put(int k)
{
	if((rear>=SIZE)
	//if((rear+1)%SIZE==front)
	{
		Uart_Printf("\n Queue overflow.");
		return -1;
	}
	queue[rear] = k;
	rear = ++rear % SIZE;
	return k;
}

int get(void)
{
	int i;
	if(rear==front)
	{
		Uart_Printf("\n Queue underflow.");
		return -1;
	}
	i=queue[front];
	front = ++front % SIZE;

	for(j=1;j<rear;j++)
		queue[j-1]=queue[j];

	return i;
}

void arrQ_main(void)
{
	int i,data;
	for(i=1;i<SIZE;i++)
		put(i); //rear에 데이터 삽입
	for(i=1;i<SIZE;i++)
	{
		data=get();	//front에서 데이터 추출
		Uart_Printf("%d ",data);
	}
}

 

- 연결리스트를 활용한 큐의 구현

#include <stdlib.h>
#include "uart.h"

#define NULL	0
 
struct node
{
     int value;
     struct node *next;
};

typedef struct node Node;

Node *front,*rear;

void InitQueue(void)
{
    front=(Node *)malloc(sizeof(Node));
    rear=(Node *)malloc(sizeof(Node));
    
    front->next=NULL;
    rear->next=NULL;
}

int Insert(int data)
{
    /* Todo 1. 리스트를 활용한 큐메모리 데이터 삽입
    */

	Node *New;
	New=(Node*)malloc(sizeof(Node));
	if(New==NULL)
	{
		UL_Printf("Queue overflow!!\n");
		return -1;
	}
    New->value=data;
    New->next = NULL;
    if(front->next==NULL) front->next = New;
    else		  rear->next->next =New;
    rear->next = New;
    
    return data;

	
}

int Delete(void)
{
	/* Todo 2. 리스트를 활용한 큐메모리 데이터 삭제
	*/

	int data;
	Node *Target;
	
     Target = front->next;// Target변수에 삭제할 노드 주소 대입(첫번째데이터)
     if(Target==NULL)	 // 만약 Target이 null이면 함수 종료    
     {
    	 UL_Printf("Queue underflow!!\n");
    	 return -1;
     }
     data = Target->value;//Target의 data를 읽어서 data변수에 저장
     front->next = Target->next;//front의 next에 Target의 next값을 전달
     free(Target);//Target 노드를 소멸시킨다.
     return data;//data를 리턴하여 전달한다.	
}
 
void FreeQueue(void)
{
     while (Delete()!=-1) {;}

     free(front);
     free(rear);
     front=NULL;
     rear=NULL;

}

void listQ_main(void)
{
	 int i;
     InitQueue();
     for (i=1;i<100;i++) {
          Insert(i);
     }
     for (i=1;i<100;i++) {
          Uart_Printf("%d  ",Delete());
     }
     FreeQueue();
}

등등 예제를 보며 구현되는 방법을 찬찬히 살펴보았다.

 

마음같아서는 책을 구입해서 각 범위마다 하나씩 찬찬히 이해해가며 공부하고 싶지만 시간 여건상 그러기는 어렵다.

따라서 이번주 교육에서는 코드를 보며 어떤 자료구조인지 파악하고, 이해할 수 있을 정도를 목표로만 학습을 \한 뒤, 후에 자료구조를 사용하거나 더 공부할 기회가 있을 때 찾아가며 꼼꼼히 공부를 해야겠다.