C언어로 stack과 queue만들기 (연결리스트 활용)

이번 42 서울을 준비하면서 다양한 라이브러리(?)를 직접 만들어야한다고 해서
몇가지를 직접 만들어보고 정리하려고 한다

오늘은 대표적인 Stack, Queue를 연결리스트로 만들어봤다

스택 만들기 이론

스택은 맨 마지막에 들어온 노드를 맨 처음으로 빼서 주는 FILO 방식의 자료구조 이다!!
흔히 호리병 등에 담겨있는 공을 뺄 때 사용된다고 생각하면 편하다.

여기서는 몇가지 단계로 나눠서 실습했다
1. Node구조체를 만들어서 data를 넣는다, 그리고 다음 주소를 가리킬 next 노드도 넣기
2. Stack 구조체를 만들어서 top 노드만 설정해둔다! (스택은 이것만 있으면 됨!)
3. 각각의 push, pop. init, isEmpty 함수를 만든다

스택 만들기 실습

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

typedef struct Node {
	int data;
    struct Node *next; //Node안에서 자기 자신을 참조하려면 struct를 붙여주기!!
}Node;

typedef struct Stack {
	Node *top; // 구조체에 화살표로 접근하기 위해 *로 지정했다!
}Stack;

void InitStack(Stack *stack);//스택 초기화
int IsEmpty(Stack *stack); //스택이 비었는지 확인
void Push(Stack *stack, int data); //스택에 보관
int Pop(Stack *stack); //스택에서 꺼냄

int main(void)
{
    int i;
    Stack stack;

    InitStack(&stack);//스택 초기화
    for (i = 1; i <= 5; i++)//1~5까지 스택에 보관
    {
        Push(&stack, i);
    }
    while (!IsEmpty(&stack))//스택이 비어있지 않다면 반복
    {
        printf("%d ", Pop(&stack));//스택에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}

void InitStack(Stack *stack) {
	stack->top=NULL; 
}
int IsEmpty(Stack *stack){
	return stack->top==NULL;
}
void Push(Stack *stack, int data){
	Node *now = (Node *)malloc(sizeof(Node));
    now->data = data;
    now->next = stack->top; // 나중에 없애게 되면 top의 그 전 노드를 주기 위해서!
    stack->top= now; // 맨 위에가 now 노드로 설정!

}
int Pop(Stack *stack){
	if(stack->top==NULL) {
    	printf("꽉 찼다!!");
        return 0;
    }
    int re;
    Node *now;
    now = stack->top;
    re = now->data; 
    stack->top = now->next; // 맨 마지막의 next에는 그 전 노드의 주소가 들어있다!!
    free(now);
    return re;
}

큐 만들기 이론

큐는 스택보다 조금 더 함수의 복잡함이 추가된다!
왜냐하면 뒤로 들어와서 앞에 있는 숫자부터 나가기 때문에!!

하지만 연결리스트를 사용했기 때문에 큰 틀은 달라지지 않는다!
앞부분 노드를 front, 맨 뒤 노드를 rear로 설정하기

큐 만들기 실습

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

typedef struct Node {
	int data;
    struct Node *next;
}Node;

typedef struct Queue {
	Node *front;
    Node *rear;
    int count;
}Queue;

void InitQueue(Queue *queue); // z큐 초기화
int IsEmpty(Queue *queue); 
void Enqueue(Queue *queue, int data); // push
int Dequeue(Queue *queue);

int main(void)
{
    int i;
    Queue queue;

    InitQueue(&queue);//큐 초기화
    for (i = 1; i <= 5; i++)//1~5까지 큐에 보관
    {
        Enqueue(&queue, i);
    }
    while (!IsEmpty(&queue))//큐가 비어있지 않다면 반복
    {
        printf("%d ", Dequeue(&queue));//큐에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}

void InitQueue(Queue *queue){
	queue->front=queue->rear = NULL;
    queue->count=0;
}
int IsEmpty(Queue *queue){
	return queue->count ==0;
}
void Enqueue(Queue *queue, int data){
	Node *now = (Node *)malloc(sizeof(Node));
    now->data = data;
    now->next=NULL;
    
    if(IsEmpty(queue)) {
    	queue->front= now;
    } else {
    	queue->rear->next = now;
        // dequeue했을때 다음 주소를 전달해주기 위해서!
    }
    queue->rear=now;
    queue->count++;
}
int Dequeue(Queue *queue){
	int re = 0;
    Node *now;
    if(IsEmpty(queue)) { return re; }
    
    now = queue->front;
    re = now->data;
    queue->front = now->next;
    free(now);
    queue->count--;
    return re;
}