[Data Structures] Stack and Queue (스택과 큐)

Stack

입력과 출력이 한 곳(Top)에서만 발생하는 자료구조이다.

LIFO(Last In First Out) : 가장 나중에 들어간 것이 가장 먼저 나온다.

함수의 콜 스택, DFS 등에서 사용된다.

 

다음은 스택의 ADT이다.

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
typedef int ElementType;
typedef int bool;

struct Node
{
    ElementType Element;
    PtrToNode Next;
};

Stack CreateStack();
bool isEmpty(Stack);
void MakeEmpty(Stack);
void Push(ElementType, Stack);
ElementType Top(Stack);
void Pop(Stack);

 

다음은 스택의 구현체이다.

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

Stack CreateStack()
{
    Stack S = malloc(sizeof(Stack));
    S->Next = NULL;
    return S;
}

bool isEmpty(Stack S)
{
    if (S->Next == NULL)
        return 1;
    else
        return 0;
}

void MakeEmpty(Stack S)
{
    while (!isEmpty(S))
        Pop(S);
}

void Push(ElementType X, Stack S)
{
    PtrToNode tmp = malloc(sizeof(PtrToNode));
    tmp->Element = X;
    tmp->Next = S->Next;
    S->Next = tmp;
}

ElementType Top(Stack S)
{
    return S->Next->Element;
}

void Pop(Stack S)
{
    PtrToNode FirstCell = S->Next;
    S->Next = S->Next->Next;
    free(FirstCell);
}

 

Queue

입력이 rear에서, 출력이 front에서 발생하는 자료구조이다.

FIFO(First In First Out) : 가장 먼저 들어간 것이 가장 먼저 나온다.

버퍼, BFS 등에서 사용 된다.

 

다음은 큐의 ADT이다.

struct Node;
struct Queue;
typedef struct Node *PtrToNode;
typedef struct Queue *PtrToQueue;
typedef PtrToNode Node;
typedef PtrToQueue Queue;
typedef int ElementType;
typedef int bool;

struct Node
{
    ElementType Element;
    PtrToNode Next;
};

struct Queue
{
    Node front;
    Node rear;
};

Queue CreateQueue();
bool isEmpty(Queue);
void Enqueue(ElementType, Queue);
ElementType Front(Queue);
ElementType Dequeue(Queue);

 

다음은 큐의 구현체이다.

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

Queue CreateQueue()
{
    Queue Q = malloc(sizeof(Queue));
    Q->front = NULL;
    Q->rear = NULL;
    return Q;
}

bool isEmpty(Queue Q)
{
    if (Q->front == NULL)
        return 1;
    else
        return 0;
}

void Enqueue(ElementType X, Queue Q)
{
    PtrToNode tmp = malloc(sizeof(PtrToNode));
    tmp->Next = NULL;
    tmp->Element = X;

    if (isEmpty(Q))
    {
        Q->front = tmp;
        Q->rear = tmp;
    }
    else
    {
        Q->rear->Next = tmp;
        Q->rear = tmp;
    }
}

ElementType Front(Queue Q)
{
    return Q->front->Element;
}

ElementType Dequeue(Queue Q)
{
    PtrToNode FirstCell = Q->front;
    Q->front = Q->front->Next;
    ElementType retElement = FirstCell->Element;
    free(FirstCell);
    return retElement;
}